大家好,欢迎来到IT知识分享网。
预热知识
=
,
=
=n*(n-1)*(n-2)*….*(n-m+1),
=
=
二项式定理:=
1.递推法(杨辉三角)
从 n个数不同的数中选出 m个的方案数是 ,对第一个数有选和不选两种决策;
若不选,则从剩下的 n-1个中选 m个,即;
若选,则从剩下的 n-1个中选 m-1个,即。
所以递推式 =
+
根据公式我们发现和杨辉三角一样,
当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.快速幂+乘法逆元
因为组合数太大,算法竞赛中常见问题是求解组合数取模%p(其中p为质数),
=
在取模的条件下,除以一个数等价于乘以这个数的乘法逆元,例如,x /2%107=x*54%107,那么54就是 2在模107条件下的乘法逆元
1.求阶乘,求出n!,m!,(n-m)! %p,for循环递推即可,每次乘法后取模
2.求出m!,(n-m)! 的乘法逆元(%p),因为p为质数,所以 x的逆元即 ,用快速幂即可求出
易得,=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