1 条题解

  • 0
    @ 2026-11-15 17:07:48

    考察内容:动态规划

    题目难度对标codeforces 1800,大概在CSP-S 第二题难度

    20pts

    对于 n≤20n \leq 20,可以直接枚举 2n2^{n}​ 的所有子集,计算所有情况。

    40pts

    初始时把所有数模 kk,把 a[i]/ka[i]/k 乘上 2N−12^{N-1} 相加,从而让 a[i]<ka[i]<k。

    对于 n,k≤100n,k \leq 100,利用背包计算出和为 x,x∈[1,nk]x,x \in [1,nk] 的子集有多少个,逐一计算 x/kx/k 的答案,复杂度为 O(n2k)O(n^2k)

    另外40pts

    对于 gcd⁡(p,k)=1\gcd(p,k)=1,注意到 kk 关于 pp 存在逆元。

    $$\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}$$

    注意后面的两项中,∑i=1∣b∣bi mod p\sum_{i=1}^{|b|}b_i \bmod p 和 ∑i=1∣b∣bi mod k) mod p\sum_{i=1}^{|b|} b_i \bmod k) \bmod p 都可以通过 DP 直接求解,而 kk​ 的逆元可以利用exgcd\text{exgcd} 表示出来,所以直接代入式子即可得出答案。

    100 pts

    对于 100%100\% 的数据:

    可以用 f[i][j]f[i][j] 表示考虑了前 ii 个数,这些数共有 2i−12^i-1 个子序列,其中子序列中所有数之和模 kk 为 jj 的有多少个。

    考虑从 ii 转移到 i+1i+1,有两种可能

    1. j+a[i+1]≥kj+a[i+1] \geq k,此时会多出 11 的贡献,把答案乘上 2N−i−1×f[i][j]2^{N-i-1} \times f[i][j],即后面每个数任取的方案,再进行正常DP转移。
    2. j<kj < k 直接正常DP转移即可。

    把所有贡献相加即为答案。

    • 1

    信息

    ID
    149
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者