首页 > 代码库 > 关于组合数求法的简单记录
关于组合数求法的简单记录
组合数 C(n,m) 从n个物品中取m个的方法数
1、当n和m比较的小的时候可以使用杨辉三角对应的数直接计算
int c[N][N]; memset(c,0,sizeof(c)); int i,j; for(i=0;i<=N;i++) { c[i][0]=c[i][i]=1; for(j=1;j<i;j++) c[i][j]=c[i-1][j-1]+c[i-1][j]; }O(N^2),显然差不多1000左右吧,取模可以直接加上。
二、当n和m比较小,mod比较大且是素数的时候,可以通过预处理逆元计算
ll inverse[N]; ll power(ll a,ll b) //关于逆元 其实如果mod是素数 则b的逆元其实就是b^(mod-2) { ll ans=1; while(b) { if(b&1) ans=(ans*a)%mod; a=(a*a)%mod; b>>=1; } return ans; } ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } ll t,r=exgcd(b,a%b,x,y); t=x; x=y; y=t-a/b*y; return r; } ll get_inverse(ll a) //exgcd求逆元 { ll x,y; exgcd(a,mod,x,y); return (x%mod+mod)%mod; } ll fc(ll n,ll m) { /*ll t1,t2; //数据小的话直接乘起来最后求一次逆元快 t1=t2=1; for(ll i=n;i>m;i--) { t1=(t1*i)%mod; t2=(t2*(i-m))%mod; } return t1*get_inverse(t2)%mod;*/ ll ans=1; //如果数据比较大 先预处理会用到的逆元 然后每次都乘逆元 for(ll i=n; i>m; i--) { ans=(ans*i)%mod; ans=(ans*inverse[i-m])%mod; } return ans; } int main() { for(int i=1; i<=N; i++) inverse[i]=power(i,mod-2); //预处理逆元 for(int i=1; i<=N; i++) inverse[i]=get_inverse(i); //预处理逆元 }
O(N) 左右吧
三、当n和m比较大,mod是素数且比较小的时候(10^5左右),通过Lucas定理计算
Lucas定理:求解C(n,m,mod)=Lucas(n,m,mod)
Lucas(n,m,mod)=C(n%mod,m%mod,mod)*Lucas(n/mod,m/mod,mod)
当m==0时 return 1
特别注意 C(n%mod,m%mod,mod) 会出现n<m,需要return 0
ll power(ll a,ll b,ll mod) { ll ans=1; while(b) { if(b&1) ans=(ans*a)%mod; a=(a*a)%mod; b>>=1; } return ans%mod; } ll fc(ll n,ll m,ll mod) //也可以预处理所有mod的阶乘 { if(m>n) return 0; //这里注意加 ll t1,t2; t1=t2=1; for(ll i=n; i>m; i--) { t1=(t1*i)%mod; t2=(t2*(i-m))%mod; } return (t1*power(t2,mod-2))%mod; } ll lucas(ll n,ll m,ll mod) { if(m==0) return 1; ll ans; ans=fc(n%mod,m%mod); return (ans*lucas(n/mod,m/mod,mod))%mod; }O(mod)左右吧
关于组合数求法的简单记录
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。