首页 > 代码库 > [组合数取模] 方法汇总
[组合数取模] 方法汇总
1.利用整数唯一分解定理,求(n+1-m) * (n+m)! / ( m! * (n+1)! )
任何正整数都有且只有一种方法写出其素因子幂相乘的形式。比如18= 2 * 3^2
A=(p1^k1)*(p2^k2)*(p3^k3)*(p4^k4)*......*(pn^kn) pi为素数
还有把阶层看作一个数,比m! 怎样求m!里面素数2的指数呢?
cnt=0; while(m) { m/=2; cnt+=m; } 就可以了,为什么呢?考虑m=4,则m!= 4*3*2*1, 第一次m/=2,是计算m!里面有多少个数能整除2的(有4,2),所以cnt+=2,有两个数贡献
了两个素数2,接下来第二次m/=2,是计算m!里面有多少个数能整除4的,有1个数又贡献了一个素数2.
所以先预先筛出最大范围内的素数,然后考虑每个素数就好了,关键是求出整个式子的该素数的指数是多少。
模板:
bool isprime[maxn*2+10]; int prime[maxn*2+10]; int len=0;//素数的个数 int n,m; void sieve(int n)//筛n以内的素数 { for(int i=0;i<=n;i++) isprime[i]=1; isprime[0]=isprime[1]=0; for(int i=2;i<=n;i++) if(isprime[i]) { prime[len++]=i; for(int j=2*i;j<=n;j+=i) isprime[j]=0; } } int cal(int p,int n)//计算n!里面有多少个p相乘 { int ans=0; while(n) { n/=p; ans+=n; } return ans; } int main() { sieve(maxn*2); long long ans=1;//记得要用long long cin>>n>>m; int nm=n+1-m; for(int i=0;i<len&&prime[i]<=(n+m);i++)//prime[i]<=(n+m)是因为拆成素数幂相乘的形式该素数不会大于n+m,最大(n+m)! (n+m)*(n+m-1)*(n+m-2)..... { int cnt=0;//分解为素数prime[i]的指数是多少 while(nm%prime[i]==0)//nm中有多少个prime[i],也就是把nm分解后prime[i]的指数 { nm/=prime[i]; cnt++; } cnt=cnt+cal(prime[i],n+m)-cal(prime[i],m)-cal(prime[i],n+1);//加上分子的指数再减去分母的指数 for(int j=1;j<=cnt;j++) { ans=ans*prime[i]; if(ans>=mod) ans%=mod; } } cout<<ans<<endl; return 0; }
[组合数取模] 方法汇总
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。