题解 CF582D 【Number of Binominal Coefficients】

思路不少题解已经讲得够清楚了，但现有题解缺少对这个繁琐的DP转移的详细分析。 这篇题解是给 @Kinandra 的题解的代码作**注解**的。 先引用 @Kinandra 代码的DP部分。 ```cpp 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)$ 的对数。 2. $f_{i,j,0/1,0/1}$ 表示考虑了最高位到第 $i$ 位，有 $j$ 次进位，第 $i$ 位否/是接受了第 $i-1$ 位的进位，最高位到第 $i$ 位否/是达到上界 $A$ 的 $(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$。 4. $c1$ 表示 $a'+b'<p$ 的解的个数，即**不进位**且**不受 $A$ 限制**。 5. $c2$ 表示 $a'+b'<x_i$ 的解的个数，即**不进位**且**受 $A$ 限制**但**不等于$A$**。 6. $c3$ 表示 $a'+b'\ge p$ 的解的个数，即**进位**且**不受 $A$ 限制**。 7. $c4$ 表示 $ p\le a'+b'< p+x_i$ 的解的个数，即**进位**且**受 $A$ 限制**但**不等于$A$**。这里稍微解释一下 $x_i·(2p-x_i-1)/2$ 是怎么来的。枚举 $a'+b'$ 的值，有 $$\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$$ 8. $c5$ 表示 $a'+b'+1<x_i$ 即**接受了进位**且**不进位**且**受 $A$ 限制**但**不等于 $A$**。 9. $c6$ 表示 $p\le a'+b'+1< p+x_i$ 即**接受了进位**且**进位**且**受 $A$ 限制**但**不等于 $A$**。 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在你谷竟然是紫题，这就是你谷平均水平吗，爱了爱了。