CF582D Number of Binominal Coefficients 题解

CF582D Number of Binominal Coefficients

题意

• 给定质数 $p$ 和整数 $\alpha,A$，求满足 $0 \le k \le n \le A$ 且 $p^{\alpha}|\binom nk$ 的数对 $(n,k)$ 的个数。
• $p,\alpha \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))$。

代码

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;
}