本文主要是介绍[组合数取模] 方法汇总，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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 longcin>>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;
}
这篇关于[组合数取模] 方法汇总的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
