手残忘了算0的逆元了……算到1就停了然后就挂了
其实这只是一个预处理阶乘逆元+Lucas定理算组合数的故事
设要算的取模的组合数为$Lucas(n,m)$
$Lucas(n,m)=Lucas(n/P,m/P)*C(n\%P,m\%P)\%P$ 其中P为取模的质数
其实P也可以不是质数，不过那样就要用中国剩余定理合并比较麻烦了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const long long P=10007;
long long test,n,m,fac[P+3],frac[P+3];
long long C(long long a,long long b){
if(a<b)return 0;
return fac[a]*frac[b]%P*frac[a-b]%P;
}
long long Lucas(long long a,long long b){
if(b==0)return 1;
return Lucas(a/P,b/P)*C(a%P,b%P)%P;
}
long long Qpow(long long x,long long y){
long long ans=1;x%=P;
while(y){
if(y&1)ans=ans*x%P;
x=x*x%P;
y>>=1;
}
return ans;
}
inline void Prepare(){
fac[0]=1;
for(register int i=1;i<P;i++)fac[i]=fac[i-1]*i%P;
frac[P-1]=Qpow(fac[P-1],P-2);
for(register int i=P-2;i>=0;i--)frac[i]=frac[i+1]*(i+1)%P;
}
int main(){
freopen("2982.in","r",stdin);
freopen("2982.out","w",stdout);
scanf("%lld",&test);
Prepare();
while(test--){
scanf("%lld %lld",&n,&m);
printf("%lld\n",Lucas(n,m));
}
return 0;
}
评论 (0)
