0%
组合数
定义法:
迭代公式法:
卢卡斯定理:
1 2 3 4 5 6 7
| int lucas(ll a,ll b){ if(a<p&&b<p) return C(a,b);
int res= (ll)C(a%p,b%p)*lucas(a/p,b/p)%p; return res; }
|
组合数高精度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76
| #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define MAXN 5010 using namespace std;
bool numlist[MAXN]; int prime[MAXN],cnt=0,num[MAXN]; int a,b; vector<int> res;
void Eular(){ for(int i=2;i<=5001;i++){ if(numlist[i]==0){ prime[++cnt]=i; } for(int j=1;j<=cnt&&prime[j]<=5001/i;j++){ numlist[i*prime[j]]=true; if(i%prime[j]==0) break; } } }
void mult(int a){ for(int i=0;i<res.size();i++) res[i]*=a; for(int i=0;i<res.size()-1;i++){ if(res[i]>=10){ res[i+1]+=res[i]/10; res[i]%=10; } } while(res[res.size()-1]>=10){ int u=res.size()-1; res.push_back(res[u]/10); res[u]%=10; } }
int main(){ Eular(); scanf("%d%d",&a,&b); for(int i=1;i<=cnt;i++){ int u=a; while(u){ num[i]+=u/prime[i]; u/=prime[i]; } u=b; while(u){ num[i]-=u/prime[i]; u/=prime[i]; } u=a-b; while(u){ num[i]-=u/prime[i]; u/=prime[i]; } } res.push_back(1); for(int i=1;i<=cnt;i++){ if(num[i]!=0){ for(int j=1;j<=num[i];j++){ mult(prime[i]); } } } for(int i=res.size()-1;i>=0;i--) printf("%d",res[i]); puts(""); return 0; }
|
卢卡斯定理的证明利用了循环节的知识。