题解 CF582D 【Number of Binominal Coefficients】
xht
2019-12-17 02:38:11
> [CF582D Number of Binominal Coefficients](https://codeforces.com/contest/582/problem/D)
## 题意
- 给定质数 $p$ 和整数 $c,s$，求满足 $0 \le k \le n \le A$ 且 $p^a|\binom nk$ 的数对 $(n,k)$ 的个数。
- $p,a \le 10^9$，$A < 10^{1000}$，答案对 $10^9+7$ 取模。
## 题解
库默尔定理：质数 $p$ 进制下 $a+b$ 的进位次数等于 $\binom{a+b}a$ 的标准分解式中 $p$ 的次数。
因此题意变成求 $0 \le a + b \le s$ 且 $a + b$ 在 $p$ 进制下的进位次数至少为为 $c$ 的非负整数对 $(a, b)$ 的个数。
数位 dp 即可，时间复杂度 $\mathcal O(\log_{p} s (\log s + \log_{p} s))$。
## 代码
```cpp
const int N = 4e3 + 7;
int p, c, n, a[N];
char s[N];
ll b[N];
modint f[2][2][N], g[2][2][N], ans;
int main() {
rd(p), rd(c), rds(s, n);
for (int i = 1; i <= n; i++) a[i] = s[n+1-i] - '0';
for (int i = n; i; i--) {
for (int j = 1; j < N - 1; j++) b[j] *= 10;
b[1] += a[i];
for (int j = 1; j < N - 1; j++)
if (b[j] >= p) b[j+1] += b[j] / p, b[j] %= p;
}
for (int i = 1; i <= N; ++i) a[i] = b[i];
n = N - 1;
while (n && !a[n]) --n;
if (!n) return print(0), 0;
f[1][0][0] = 1;
for (int i = n; i; i--) {
modint a0 = 1ll * p * (p + 1) / 2 % P;
modint a1 = 1ll * p * (p - 1) / 2 % P;
modint a2 = 1ll * a[i] * (a[i] + 1) / 2 % P;
modint a3 = 1ll * a[i] * (a[i] - 1) / 2 % P;
modint a4 = 1ll * a[i] * (p + p - a[i] - 1) / 2 % P;
modint a5 = 1ll * a[i] * (p + p - a[i] + 1) / 2 % P;
for (int j = 0; j <= n + 1 - i; j++) g[0][0][j] = g[0][1][j] = g[1][0][j] = g[1][1][j] = 0;
for (int j = 0; j <= n - i; j++) {
modint f0 = f[0][0][j], f1 = f[0][1][j], f2 = f[1][0][j], f3 = f[1][1][j];
g[0][0][j] += f0 * a0 + f2 * a2;
g[0][1][j] += f0 * a1 + f2 * a3;
g[1][0][j] += f2 * (a[i] + 1);
g[1][1][j] += f2 * a[i];
g[0][0][j+1] += f1 * a1 + f3 * a4;
g[0][1][j+1] += f1 * a0 + f3 * a5;
g[1][0][j+1] += f3 * (p - a[i] - 1);
g[1][1][j+1] += f3 * (p - a[i]);
}
swap(f, g);
}
for (int i = c; i <= n; i++) ans += f[0][0][i] + f[1][0][i];
print(ans);
return 0;
}
```