组合数的模运算

wayne

求 C(n,m) mod(M) 的算法。 其中n,m,M 均在int型范围内。 速度越快，内存占用越少越好， 看有没有两个都在O(n)尺度以内的算法。 问题背景：http://poj.grids.cn/practice/4036/

wayne

终于搞定了 平均的时间复杂度大致是 O(m)，(mhttp://poj.grids.cn/practice/4036/statistics/

gxqcn

这么厉害，祝贺祝贺！ 我想应该用到一些数学上的优化以及内嵌汇编吧？

wayne

3# gxqcn 没有什么数学方法，就是模拟了一下最基础的约分化简过程。 应该还能优化的

1. #include <stdio.h>
2. #define MOD 10007
4. int gcd(int m,int n)
5. {
6. int t ;
7. while(m!=0)t=m,m=n%m,n=t ;
8. return n ;
9. }
11. int binomialMod(int k,int n,int mod)
12. {
13. int c,g,ii,jj,p[n],q[n];
14. /*C(k,n)= p1/q1*p2/q2*p3*q3....pn*qn */
15. for(ii=0;ii<n;ii++)p[ii]=k-ii ;
16. for(ii=n;ii>=1;ii--)
17. {
18. c=k%ii ;
19. g=gcd(p[c],ii);
20. p[c]/=g ;
21. q[ii-1]=ii/g ;
22. /*when ii<n/2, there are more reduction work */
23. if(q[ii-1]!=1)
24. {
25. jj=0 ;
26. while(q[ii-1]!=1&&c+jj<n)
27. {
28. c=k%q[ii-1];
29. g=gcd(p[c+jj],q[ii-1]);
30. p[c+jj]/=g ;
31. q[ii-1]/=g ;
32. jj+=g ;
33. }
34. }
35. }
37. c=1 ;
38. for(ii=0;ii<n;ii++)
39. {
40. c*=p[ii];
41. c%=mod;
42. }
43. return c ;
44. }
46. int powMod(int a,int pow,int mod)
47. {
48. int ii=0,s=1 ;
49. while(++ii<=pow)s*=a,s%=mod ;
50. return s ;
51. }
53. int main()
54. {
55. int a,b,k,n,m,ii,s ;
56. scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
58. a%=MOD ;
59. b%=MOD ;
60. s=1 ;
61. s*=powMod(a,n,MOD);
62. s*=powMod(b,m,MOD);
63. s%=MOD ;
64. s*=binomialMod(k,n,MOD);
65. s%=MOD ;
66. printf("%d",s);
68. return 0 ;
69. }

复制代码

gxqcn

上面 Line 49 中的“s*=a” 恐有溢出风险吧？

wayne

5# gxqcn 老大说的对。 呵呵，这题竟然被我蒙混过关了， 。 ========= 另外，如果指数比较大的话，一个一个的乘还会很慢。

mathe

其实现将M因子分解是不错的方法，花费时间也不大，不会超过O(sqrt(M)) 然后计算M每个素因子在C(n,m)的次数，在然后计算因子乘积关于M(或其某个因子)的余数即可

wayne

6# wayne 上面的 binomialMod，powMod 函数仅对 MOD小于 sqrt(MAX_INT) 有效，而题目的MOD是 10007。

1. int powMod(int a,int pow,int mod){
2. if (pow==0) return 1;
3. a%=mod;
4. int s= powMod(a*a, pow/2, mod);
5. if (pow%2 !=0) s*=a,s%=mod;
6. return s;
7. }

复制代码

wayne

7# mathe 如果 M是素数，而且比较大，比如10007，该怎么考虑

wayne

感觉在INT范围内，计算两个INT的乘积的模，还需要单独考虑