首页 > 代码库 > 组合数计算C(n,m)加取模情况
组合数计算C(n,m)加取模情况
想法:以前做比赛的时候遇到很多需要计算组合数的情况,都是当时手敲的,写递归不是暴就是超时啥的,或者是因为要取模,然后还要求逆元,所以敲得不是慢就是老是出问题,所以现在搞出模板来以后用就快了。
一:线性求C(n,m)
解释:由HDU 4927这道题求的组合数,可以了解到组合数的一些递推快速求法,因为这道题就是卡组合数的时间的。如果我们要算C(10,4),我们可以先算C(10,1),再算C(10,2),再算C(10,3),再算C(10,4)。为什么我要这么求呢?
因为:C(10,1)=10/1,然后C(10,1)*9/2就等于C(10,2)了,即C(10,2)=10*9/(2*1);然后C(10,2)*8/3就等于C(10,3)了,即C(10,3)=10*9*8/(3*2*1);然后C(10,3)*7/4就等于C(10,4)了,即C(10,4)=10*9*8*7/(4*3*2*1)。刚开始我还担心分子除以分母的时候可能会不得整除呢,但是放心,已经证明过了,可以这样递推的计算,得到的每个组合肯定是对的,不会出现小数点的情况。
所以根据这个性质或者说规律,可以用代码线性的求出C(n,m)了:
ll combine1(ll n,ll m) //计算组合数C(n,m) { ll sum=1; //线性计算 for(ll i=1,j=n;i<=m;i++,j--) sum=sum*j/i; return sum; }
由c(n,m)=c(n-1,m-1)+c(n-1,m),我们可以轻易的用代码递归得出C(n,m)的值:
ll combine2(ll n,ll m) //计算组合数C(n,m) { if(n==m||!m) return 1;//递归计算 return combine2(n-1,m)+combine2(n-1,m-1); }两种比较:线性的求组合数是很快的,每次只从1求到m即可;但是递归就不行了,计算C(50,25)的时候已经严重超时并暴了,等了好久都得不出答案,所以以后和线性的代码吧!
三:用线性求C(n,m)%mod
void extend_gcd(ll a,ll b,ll &d,ll &x,ll &y) { if(!b) d=a,x=1,y=0; else { extend_gcd(b,a%b,d,y,x); y-=x*(a/b); } } ll Mod(ll a,ll b,ll mod)//算出的逆元不对,明天检查一下才行 { if(!b) return 1; ll ans=Mod(a,b>>1,mod); ans=ans*ans%mod; if(b&1) ans=ans*a%mod; return ans; } ll inv(ll a,ll mod)//计算a对mod的逆元 { ll d,x,y; extend_gcd(a,mod,d,x,y); return d==1?(x+mod)%mod:-1; //return Mod(a,mod-2,mod); } ll combine1(ll n,ll m,ll mod)//计算组合C(n,m)%mod { ll sum=1; //线性计算 for(ll i=1,j=n; i<=m; i++,j--) sum=sum*j*inv(i,mod)%mod; return sum; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。