! SHOI2015超能粒子炮·改

根据\(lucas\)定理：\(C_n^m\%p=C_{n/p}^{m/p}*C^{m\%p}_{n\%p}\%p\)

（组合数大模数小用\(lucas\)）

预处理+搜索（\(C_{n/p}^{k/p}\)直接上\(lucas\)）

时间复杂度\(O(p^2+Tlog_p^2n)\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=2333;
ll f[mod][mod],c[mod][mod];
ll lucas(ll n,ll m){
	if(!m||n==m)return 1;
	if(n<m)return 0;
	return c[n%mod][m%mod]*lucas(n/mod,m/mod)%mod;
} 
ll F(ll n,ll k){
	if(k<0)return 0;
	if(!n||!k)return 1;
	if(n<mod&&k<mod)return f[n][k];
	return (F(n/mod,k/mod-1)*f[n%mod][mod-1]+lucas(n/mod,k/mod)*f[n%mod][k%mod])%mod;
}
inline void pre(){
	for(int i=0;i<mod;i++){
		c[i][0]=1;
		for(int j=1;j<=i;j++)
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%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;
	}
}
int main(){
	pre();
	int T;
	scanf("%d",&T);
	while(T--){
		static ll n,k;
		scanf("%lld%lld",&n,&k);
		cout<<F(n,k)<<"\n"; 
	}
	return (0-0);
}

! SHOI2015超能粒子炮·改

原文：https://www.cnblogs.com/aurora2004/p/12561983.html