P4345 [SHOI2015]超能粒子炮·改 Lucas

(color{#0066ff}{ 题目描述 })

曾经发明了脑洞治疗仪与超能粒子炮的发明家 SHTSC 又公开了他的新发明：超能粒子炮・改——一种可以发射威力更加强大的粒子流的神秘装置。

超能粒子炮・改相比超能粒子炮，在威力上有了本质的提升。它有两个参数(n),(k)，它会向每个编号为(0)到(k)（包含两端）的位置(i)发射威力为(C_{n}^{i} mod 2333)的粒子流。

现在 SHTSC 给出了他的超能粒子炮・改的参数，让你求出其发射的粒子流的威力之和除以(2333)所得的余数。

(color{#0066ff}{输入格式})

第一行一个整数(t)表示数据组数。之后 (t) 行，每行两个整数 (n)、(k)，含义如题面描述。

(color{#0066ff}{输出格式})

t 行，每行一个整数，表示其粒子流的威力之和模 2333 的值。

(color{#0066ff}{输入样例})

(color{#0066ff}{输出样例})

32
968
763

(color{#0066ff}{数据范围与提示})

(color{#0066ff}{ 题解 })

令(p=2333, f(n,k)=egin{aligned}sum_{i=0}^kC_n^iend{aligned})

考虑将([0,k])分成一些段

可以发现，对于(iin [0, p*lfloorfrac k p floor))，分成了(lfloorfrac k p floor)段，每段长度为p，根据((lfloorfrac i p floor, i \% p))可以唯一确定一个i

据Lucas定理，有(C_n^i=C_{n/p}^{i/p}*C_{n\%p}^{i\%p})

根据乘法原理，贡献为(f(lfloorfrac n p floor,lfloorfrac k p floor - 1)*f(n\%p,p-1))

考虑剩下的部分，(iin[p*lfloorfrac k p floor,k])

显然剩下部分的(lfloor frac i p floor)是一样的

贡献为(C_{n/p}^{k/p}*f(n\%p,k\%p))

于是，总贡献为(f(n,k)=C_{n/p}^{k/p}f(n\%p,k\%p)+f(lfloorfrac n p floor,lfloorfrac k p floor - 1)f(n\%p,p-1))

预处理出p以内的f值，在预处理阶乘和逆元之后，(O(p^2))就能处理，这些值调用比较频繁

剩下的C直接Lucas就行了

#include<bits/stdc++.h>
#define LL long long
LL in() {
	char ch; LL x = 0, f = 1;
	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
	return x * f;
}
const int mod = 2333;
const int maxn = 3e3 + 10;
LL f[maxn][maxn], fac[maxn], inv[maxn];
LL ksm(LL x, LL y) {
	LL re = 1LL;
	while(y) {
		if(y & 1) re = re * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return re;
}
LL C(LL n, LL m) {
	if(m > n || m < 0) return 0;
	if(n >= mod || m >= mod) return C(n / mod, m / mod) * C(n % mod, m % mod) % mod;
	return ((fac[n] * inv[m] % mod) * inv[n - m]) % mod;
}
LL work(LL n, LL k) {
	if(n < mod && k < mod) return f[n][k];
	return ((C(n / mod, k / mod) * work(n % mod, k % mod) % mod) + (work(n / mod, k / mod - 1) * work(n % mod, mod - 1) % mod)) % mod;
}
void predoit() {
	fac[0] = 1;
	for(int i = 1; i < mod; i++) fac[i] = 1LL * i * fac[i - 1] % mod;
	inv[mod - 1] = ksm(fac[mod - 1], mod - 2);
	for(int i = mod - 2; i >= 0; i--) inv[i] = 1LL * inv[i + 1] * (i + 1) % mod;
	for(int i = 0; i < mod; i++) {
		f[i][0] = 1;
		for(int j = 1; j < mod; j++)
			f[i][j] = (f[i][j - 1] + C(i, j)) % mod;
	}
}
signed main() {
	predoit();
	for(int T = in(); T --> 0;) {
		LL n = in(), k = in();
		printf("%lld
",  work(n, k));
	}
	return 0;
}