【算法】組合數(shù)取模——lucas定理

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int p=10007; int fac[p+10],inv[p+10]; void gcd(int a,int b,int &x,int &y) {if(b==0){x=1;y=0;}else{gcd(b,a%b,y,x);y-=x*(a/b);} } void pre_inv() {fac[0]=fac[1]=1;for(int i=2;i<p;i++)fac[i]=(fac[i-1]*i)%p;int xx,yy;gcd(fac[p-1],p,xx,yy);inv[p-1]=((xx%p)+p)%p;//擴(kuò)歐解不一定是最小非負(fù)解！ for(int i=p-2;i>=0;i--)inv[i]=(inv[i+1]*(i+1))%p; } int C(int n,int m) {if(n<m)return 0;if(n<p&&m<p)return (1ll*fac[n]*inv[m]*inv[n-m])%p;return (C(n%p,m%p)*C(n/p,m/p))%p; } int main() {pre_inv();int T,n,m;scanf("%d",&T);//for(int i=0;i<10;i++)printf("inv_%d=%d\n",i,inv[i]);while(T--){scanf("%d%d",&n,&m);printf("%d\n",C(n,m));}return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/onioncyc/p/7136684.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ】2982 combination的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。