LOJ 2038 超能粒子炮・改

题目链接

题目

求\(\sum\limits_{i=0}^{k}\binom{n}{i}\bmod 2333\)
## 分析
用卢卡斯定理拆组合数。
\(\sum\limits_{i=0}^{k}\binom{n/p}{i/p}\binom{n\bmod p}{i\bmod p}\bmod 2333\)

观察一下发现等于,
\(\binom{n/p}{0}\sum\limits_{i=0}^{p-1}\binom{n\bmod p}{i}+\binom{n/p}{1}\sum\limits_{i=0}^{p-1}\binom{n\bmod p}{i}+\binom{n/p}{2}\sum\limits_{i=0}^{p-1}\binom{n\bmod p}{i}+\text{...}+\binom{n/p}{k/p}\sum\limits_{i=0}^{k\bmod p}\binom{n\bmod p}{i}\)

也就是\(\left\{\binom{n/p}{0}+\binom{n/p}{1} +\text{...}+{\binom{n/p}{n/p-1}}\right\}\times \sum\limits_{i=0}^{p-1}\binom{n\bmod p}{i}+\binom{n/p}{k/p}\sum\limits_{i=0}^{k\bmod p}\binom{n\bmod p}{i}\)

我们令\(f(n,k)\)表示\(\sum\limits_{i=0}^{k}\binom{n}{i} \bmod 2333\)
则\(f(n,k)=f(n/p,n/p-1)\times f(n\bmod p,p-1)+f(n\bmod p,k\bmod p)\times \binom{n/p}{k/p}\)
显然取模的可以暴力预处理，除号用卢卡斯定理。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2345, MOD = 2333;
int T, n, k, f[N][N], c[N][N];

int lucas(int n, int m) {
	if (m == 0) return 1;
	return lucas(n / MOD, m / MOD) * 1ll * c[n % MOD][m % MOD] % MOD;
}
int F(int n, int k) {
	if (k < 0) return 0;
	if (n == 0) return 1;
	if (k == 0) return 1;
	if (n < MOD && k < MOD) return f[n][k];
	return (F(n / MOD, k / MOD - 1) * 1ll * f[n % MOD][MOD - 1] % MOD + lucas(n / MOD, k / MOD) * 1ll * f[n % MOD][k % MOD] % MOD) % MOD;
}

main() {
	scanf("%lld", &T);
	c[0][0] = 1;
    for (int i = 1; i < N; i++)
		for (int j = 0; j <= i; j++) {
			if (j == 0 || j == i) c[i][j] = 1;
			else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
		}
	f[0][0] = 1;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			if (j == 0) f[i][j] = c[i][j];
			else f[i][j] = (f[i][j - 1] + c[i][j]) % MOD;
		}
	while (T--) {
		scanf("%lld %lld", &n, &k);
        printf("%lld\n", F(n, k));
	}
	return 0;
}