组合数(三种求法)

组合数(三种求法)从 n 个数不同的数中选出 m 个的方案数是 对第一个数有两种决策 若不选 则从剩下的 n 1 个中选 m 个 即 若选 则从剩下的 n 1 个中选 m 1 个 即

大家好,欢迎来到IT知识分享网。

预热知识

C_{n}^{m}=C_{n}^{n-m}A_{n}^{m}=\frac{n!}{m!}=n*(n-1)*(n-2)*….*(n-m+1),C_{n}^{m}=\frac{A^{_{n}^{m}}}{A_{n}^{n}}=\frac{n!}{(n-m)!}

二项式定理:(a+b)^{n}=\sum_{i=0}^{n}C_{n}^{i}a^{i}b^{n-i}

1.递推法(杨辉三角)

从 n个数不同的数中选出 m个的方案数是 C_{n}^{m},对第一个数选和不选两种决策;

若不选,则从剩下的 n-1个中选 m个,即C_{n-1}^{m}

若选,则从剩下的 n-1个中选 m-1个,即C_{n-1}^{m-1}

所以递推式 C_{n}^{m}=C_{n-1}^{m}+C_{n-1}^{m-1}

根据公式我们发现和杨辉三角一样,C_{n}^{m}当n==1,m=0时,为1;当n==3,m==2时,为3。m,n数据小的时候我们可以用递推,但如果数据范围太大就要用其他方法

组合数(三种求法)

void getc(){ for(int i=0;i<n;i++){ for(int j=0;j<=i;j++){ if(j==0) a[i][j]=1; //数组a存储的是n=i,m=j的组合数 else{ a[i][j]=(a[i-1][j]+a[i-1][j-1])%mod; } } } }

2.快速幂+乘法逆元

因为组合数太大,算法竞赛中常见问题是求解组合数取模C_{n}^{m}%p(其中p为质数),C_{n}^{m}=\frac{n!}{(n-m)!}

在取模的条件下,除以一个数等价于乘以这个数的乘法逆元,例如,x /2%107=x*54%107,那么54就是 2在模107条件下的乘法逆元

1.求阶乘,求出n!,m!,(n-m)!  %p,for循环递推即可,每次乘法后取模

2.求出m!,(n-m)! 的乘法逆元(%p),因为p为质数,所以 x的逆元即 x^{p-2},用快速幂即可求出

易得,C_{n}^{m}=inf[n] * (fa[m]的逆元)*(fa[n-m]的逆元),总时间复杂度为O(n)

int qmi(int a,int b,int p){ int res=1; while(b){ if(b&1) res=res*a%p; n=a*a%p; b>>=1; } return res; //快速幂 } void init(){ fa[0]=inf[0]=1; for(int i=1;i<N-10;i++){ fa[i]=fa[i-1]*i%p; //fa为阶乘数组 inf[i]=inf[i-1]*qmi(i,p-2,p)%p; //计算逆元 } } int C(int n,int m,int p){ int ans=0; if(m>n)return 0; return fa[n]%p*inf[m]%p*inf[n-m]%p; //inf为求得的逆元数组 }

3.卢卡斯定理

组合数(三种求法)

前半部分可以继续使用卢卡斯定理递归求解,后半部分可以用第二种方法直接求解,后半部分的m,n都会小于p,时间复杂度为O(n)。适用于n较大,p较小或n较小的情况

int lucas(int a,int b,int p){ if(a<p&&b<p)return C(a,b,p); return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p; //前半部分为方法二中的函数,后半部分为递归 } 

4.例题

这是一道卢卡斯定理的模板题 

组合数(三种求法)

 例题链接

#include<iostream> #include<algorithm> #include<cstring> #define int long long using namespace std; const int N = 1e5+10; int inf[N],fa[N]; int T; int n,m,p; int qmi(int a,int b,int p){ int res=1; while(b){ if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } void init(){ fa[0]=inf[0]=1; for(int i=1;i<N-10;i++){ fa[i]=fa[i-1]*i%p; inf[i]=inf[i-1]*qmi(i,p-2,p)%p; } } int C(int a,int b,int p){ int ans=0; if(b>a)return 0; return fa[a]%p*inf[b]%p*inf[a-b]%p; } int lucas(int a,int b,int p){ if(a<p&&b<p)return C(a,b,p); return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p; } //前半部分为方法二中的函数,后半部分为递归 signed main(){ cin>>T; while(T--){ cin>>n>>m>>p; init(); cout<<lucas(n+m,m,p)<<endl; } return 0; }

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/127956.html

(0)
上一篇 2025-09-03 22:10
下一篇 2025-09-03 22:15

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信