组合数的模运算
求 C(n,m)mod(M) 的算法。其中n,m,M 均在int型范围内。
速度越快，内存占用越少越好，
看有没有两个都在O(n)尺度以内的算法。
问题背景：http://poj.grids.cn/practice/4036/ 终于搞定了
平均的时间复杂度大致是 O(m)，(m<n) ,
空间复杂度 O(m).
http://poj.grids.cn/practice/4036/statistics/ 这么厉害，祝贺祝贺！
我想应该用到一些数学上的优化以及内嵌汇编吧？ 3# gxqcn
:loveliness:
没有什么数学方法，就是模拟了一下最基础的约分化简过程。
应该还能优化的#include <stdio.h>
#define MOD 10007
int gcd(int m,int n)
{
int t ;
while(m!=0)t=m,m=n%m,n=t ;
return n ;
}
int binomialMod(int k,int n,int mod)
{
int c,g,ii,jj,p,q;
/*C(k,n)= p1/q1*p2/q2*p3*q3....pn*qn */
for(ii=0;ii<n;ii++)p=k-ii ;
for(ii=n;ii>=1;ii--)
{
c=k%ii ;
g=gcd(p,ii);
p/=g ;
q=ii/g ;
/*when ii<n/2, there are more reduction work */
if(q!=1)
{
jj=0 ;
while(q!=1&&c+jj<n)
{
c=k%q;
g=gcd(p,q);
p/=g ;
q/=g ;
jj+=g ;
}
}
}
c=1 ;
for(ii=0;ii<n;ii++)
{
c*=p;
c%=mod;
}
return c ;
}
int powMod(int a,int pow,int mod)
{
int ii=0,s=1 ;
while(++ii<=pow)s*=a,s%=mod ;
return s ;
}
int main()
{
int a,b,k,n,m,ii,s ;
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
a%=MOD ;
b%=MOD ;
s=1 ;
s*=powMod(a,n,MOD);
s*=powMod(b,m,MOD);
s%=MOD ;
s*=binomialMod(k,n,MOD);
s%=MOD ;
printf("%d",s);
return 0 ;
}
上面 Line 49 中的“s*=a” 恐有溢出风险吧？ 5# gxqcn
老大说的对。
呵呵，这题竟然被我蒙混过关了，:L 。
=========
另外，如果指数比较大的话，一个一个的乘还会很慢。 其实现将M因子分解是不错的方法，花费时间也不大，不会超过O(sqrt(M))
然后计算M每个素因子在C(n,m)的次数，在然后计算因子乘积关于M(或其某个因子)的余数即可 6# wayne
上面的 binomialMod，powMod 函数仅对 MOD小于 sqrt(MAX_INT) 有效，而题目的MOD是 10007。int powMod(int a,int pow,int mod){
if (pow==0) return 1;
a%=mod;
int s= powMod(a*a, pow/2, mod);
if (pow%2 !=0) s*=a,s%=mod;
return s;
} 7# mathe
如果 M是素数，而且比较大，比如10007，该怎么考虑 感觉在INT范围内，计算两个INT的乘积的模，还需要单独考虑