1 条题解
-
0
考察内容:动态规划
题目难度对标codeforces 1800,大概在CSP-S 第二题难度
20pts
对于 ,可以直接枚举 的所有子集,计算所有情况。
40pts
初始时把所有数模 ,把 乘上 相加,从而让 。
对于 ,利用背包计算出和为 的子集有多少个,逐一计算 的答案,复杂度为
另外40pts
对于 ,注意到 关于 存在逆元。
$$\lfloor \frac{\sum_{i=1}^{|b|} b_i}{k} \rfloor=\frac{\sum_{i=1}^{|b|}b_i-(\sum_{i=1}^{|b|} b_i \bmod k)}{k}=\frac{\sum_{i=1}^{|b|}b_i}{k}-\frac{(\sum_{i=1}^{|b|} b_i \bmod k)}{k}$$注意后面的两项中, 和 都可以通过 DP 直接求解,而 的逆元可以利用 表示出来,所以直接代入式子即可得出答案。
100 pts
对于 的数据:
可以用 表示考虑了前 个数,这些数共有 个子序列,其中子序列中所有数之和模 为 的有多少个。
考虑从 转移到 ,有两种可能
- ,此时会多出 的贡献,把答案乘上 ,即后面每个数任取的方案,再进行正常DP转移。
- 直接正常DP转移即可。
把所有贡献相加即为答案。
- 1
信息
- ID
- 149
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者