lucas-超能粒子炮-改

[lucas]超能粒子炮-改

BZOJ4591

求$\sum_{i=0} ^{k} (^n_ i) mod 2333,(k<=n<=10^{18})$

令$f(n,k)$为题目的答案。
设$p=2333,a=k/p,b=k\%p$,则：(以下均在$mod p$意义下进行）

$f(n,k) \equiv \sum_{i=0} ^{k} (^n_ i)$

$f(n,k) \equiv \sum_ {i=0} ^{ap-1}(^n_ i)+\sum_ {i=ap}^{ap+b}(^n_ i)$

$f(n,k) \equiv \sum_{i=0} ^{ap-1} (^{n/p}_ {i/p})(^{n\%p}_ {i\%p}) + \sum_{i=ap}^{ap+b}(^{n/p}_ {i/p})(^{n\%p}_{i\%p})$

把很久才变一次的$(^{n/p}_ {i/p})$提取出来

$f(n,k) \equiv \sum_{i=0}^{a-1}[(^{n/p}_ i) \times \sum_ {j=0}^{p-1}(^{n\%p}_ j)]+(^{n/p}_ a)\sum_ {i=0}^b(^{n\%p}_ i)$

由于乘法分配率前面的那一项可以拆开来

$f(n,k) \equiv \sum_{i=0}^{a-1}(^{n/p}_ i) \times \sum_ {j=0}^{p-1}(^{n\%p}_ j)+(^{n/p}_ a)\sum_ {i=0}^b(^{n\%p}_ i)$

根据定义可以把式子中的一部分改成$f()$的形式(时刻记得$f()$代表什么！！！)

$f(n,k) \equiv f(n/p,a-1) \times \sum_ {j=0}^{p-1}(^{n\%p}_ j)+(^{n/p}_ a)\sum_ {i=0}^b(^{n\%p}_ i)$

这样后面几项都小于$p$，就可以预处理解决了
前面递归就好

code:

#include<iostream>
#include<cstdio>
#include<cstring>
typedef long long lint;
const int mod=2333;
int C[mod][mod],sc[mod][mod];

template<class T> inline T nxi(){
	T x=0;
	char c;
	while((c=getchar())>'9'||c<'0');
	while(x=x*10-48+c,(c=getchar())>='0'&&c<='9');
	return x;
}

inline void twk(int &x){
	if(x>=mod) x-=mod;
}

inline void init(){
	C[0][0]=1,sc[0][0]=1;;
	for(int i=0;i<mod;++i) sc[0][i]=1;
	for(int i=1;i<mod;++i){
		sc[i][0]=C[i][0]=1;
		for(int j=1;j<mod;++j){
			twk(C[i][j]=C[i-1][j]+C[i-1][j-1]);
			twk(sc[i][j]=sc[i][j-1]+C[i][j]);
		}
	}
}

int lucas(const lint n,const lint k){
	if(k<0||n<k) return 0;
	if(n<mod) return C[n][k];
	return lucas(n/mod,k/mod)*lucas(n%mod,k%mod)%mod;
}

int sol(const lint n,const lint k){
	const int P=mod;
	if(k<0) return 0;
	if(n<P&&k<P) return sc[n][k];
	return (sol(n/P,k/P-1)*sol(n%P,n%P)+lucas(n/P,k/P)*sc[n%P][k%P])%P;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
	freopen("4591.out","w",stdout);
#endif
	init();
	int T=nxi<int>();
	while(T--){
		lint n=nxi<lint>(),k=nxi<lint>();
		printf("%d\n",sol(n,k));
	}
	return 0;
}