题解 CF582D 【Number of Binominal Coefficients】

· · 题解

思路不少题解已经讲得够清楚了，但现有题解缺少对这个繁琐的DP转移的详细分析。
这篇题解是给 @Kinandra 的题解的代码作注解的。
先引用 @Kinandra 代码的DP部分。 

void work() {
        f[len + 1][0][0][1] = 1;
        for (int i = len, c1, c2, c3, c4, c5, c6; i >= 1; --i) {
            c1 = 1ll * (p + 1) * p / 2 % mod,
            c2 = 1ll * (x[i] + 1) * x[i] / 2 % mod,
            c3 = 1ll * p * (p - 1) / 2 % mod,
            c4 = 1ll * x[i] * ((p << 1) - x[i] - 1) / 2 % mod,
            c5 = 1ll * x[i] * (x[i] - 1) / 2 % mod,
            c6 = 1ll * x[i] * ((p << 1) - x[i] + 1) / 2 % mod;

            for (int j = 0, f0, f1, f2, f3; j <= len - i + 1; ++j) {
                f0 = f[i + 1][j][0][0], f1 = f[i + 1][j][0][1],
                f2 = f[i + 1][j][1][0], f3 = f[i + 1][j][1][1];
                if (!f0 && !f1 && !f2 && !f3) continue;
                f[i][j][0][0] = (1ll * c1 * f0 % mod + 1ll * c2 * f1 % mod +
                                 1ll * c3 * f2 % mod + 1ll * c4 * f3 % mod) %
                                mod;
                f[i][j][0][1] = M(1ll * (x[i] + 1) * f1 % mod +
                                  1ll * (p - x[i] - 1) * f3 % mod);
                f[i][j + 1][1][0] =
                    (1ll * c3 * f0 % mod + 1ll * c5 * f1 % mod +
                     1ll * c1 * f2 % mod + 1ll * c6 * f3 % mod) %
                    mod;
                f[i][j + 1][1][1] =
                    M(1ll * x[i] * f1 % mod + 1ll * (p - x[i]) * f3 % mod);
            }
        }
        int res = 0;
        for (int i = alpha; i <= len; ++i)
            res = M(res + M(f[1][i][0][0] + f[1][i][0][1]));
        printf("%d\n", res);
    }

可能有点晕，别着急，我们慢慢分析。
先约定最低位为第 1 位。

  1. 令 a=k,b=n-k，那么我们要解决的问题是，求 p 进制下满足 0\le a,0\le b,a+b \le A 且 a+b 进位次数大于等于 \alpha 的 (a,b) 的对数。

  3. 第4~9点将依次解释代码中的 c1,c2,c3,c4,c5,c6 的意思，他们分别表示一个关于 a',b' 的不等式的的解的个数，该处的 a',b' 分别表示 a,b 的第 i 位，因此 0\le a',b'\le p-1。

  7. $$\sum_{i=p}^{p+x_i-1}\sum_{0\le a'}^{p-1}\sum_{0\le b'}^{p-1}[a'+b'=i]$$ $$\sum_{i=p}^{p+x_i-1}\sum_{0\le a'}^{p-1}[0\le i-a'\le p-1]$$ $$\sum_{i=p}^{p+x_i-1}\sum_{0\le a'}^{p-1}[i-p+1\le a'\le i]$$ $$\sum_{i=p}^{p+x_i-1}\sum_{a'}[\max(0,i-p+1)\le a'\le \min(p-1,i)]$$ 由于 $i-p+1>0,i>p-1$ 所以其实是 $$\sum_{i=p}^{p+x_i-1}2p-i-1=x_i·(2p-x_i-1)/2$$

  10. 现在 f_{i,j,0/1,0} 的转移应该能看懂了，第11~12点将解释 f_{i,j,0/1,1}的转移，它们都表示钦定在第 i 位上等于 x_i，区别是是否接受了进位。

  11. 对于 f_{i,j,0,1}，x[i]+1 即 a'+b'=x_i 的解的数量，p-x_i-1 即 a'+b'=p+x_i 的解的数量。

  12. 对于 f_{i,j,1,1}，x[i] 即 a'+b'+1=x_i 的解的数量，p-x_i 即 a'+b'+1=p+x_i 的解的数量。

最后吐槽一句，cf3300的dp在你谷竟然是紫题，这就是你谷平均水平吗，爱了爱了。