一、组合数的定义
组合数是数学中的一个概念,用于计算从n个不同元素中,任取k个元素的不同组合数,用C(n,k)表示。可以用以下公式计算:
C(n,k)= n! / (k!*(n-k)!);
其中,n!表示n的阶乘,即n*(n-1)*(n-2)*…*1, 0!=1。
二、暴力枚举法
最朴素的方法是通过暴力枚举所有可能的组合情况,然后计算符合要求的组合数。这种方法的时间复杂度为O(C(n,k)),在k或n较大时其效率极低。
代码示例:
#include<bits/stdc++.h> using namespace std; int main(){ int n,k; cin>>n>>k; int ans=0; for(int i=0;i<(1<<n);i++){ //枚举所有情况 if(__builtin_popcount(i)==k) ans++; //统计符合要求的情况数 } cout<三、递推法
通过C(n,k)=C(n-1,k-1)+C(n-1,k)的递推公式,可以通过存储上一步计算的结果来计算当前步的结果。这种方法的时间复杂度为O(k*(n-k)),效率相较于暴力枚举有所提高。
代码示例:
#include<bits/stdc++.h> using namespace std; const int maxn=1005; int c[maxn][maxn]; int main(){ int n,k; cin>>n>>k; for(int i=0;i<=n;i++){ for(int j=0;j<=i;j++){ if(j==0||j==i) c[i][j]=1; //边界条件 else c[i][j]=c[i-1][j-1]+c[i-1][j]; //递推公式 } } cout<<c[n][k]<<endl; return 0; }四、Lucas定理
当n和k均比较大时,使用暴力枚举和递推都不太现实。可以使用Lucas定理,将n和k分解为p进制数的形式,进而计算组合数。时间复杂度为O(logp(n)+logp(k)),其中p为模数。
代码示例:
#include<bits/stdc++.h> using namespace std; const int maxn=1005; const int mod=10007; //取模数 int fac[maxn],inv[maxn]; //预处理阶乘和逆元 int power(int a,int b,int m){ //快速幂 int ans=1%m; while(b>0){ if(b&1) ans=(ans*a)%m; a=(a*a)%m; b>>=1; } return ans; } int C(int n,int k,int m){ //计算组合数 if(n0&&k>0){ //每次取p进制数的最后一位进行计算,直至n=0或k=0 int a=n%m; int b=k%m; if(a<b) return 0; ans=(ans*C(a,b,m))%m; n/=m; k/=m; } return ans; } int main(){ fac[0]=1; for(int i=1;i=0;i--) inv[i]=(inv[i+1]*(i+1))%mod; int n,k; cin>>n>>k; cout<<Lucas(n,k,mod)<<endl; return 0; }
最新评论