组合数的模运算

wayne

求 C(n,m)  mod(M) 的算法。
其中n,m,M 均在int型范围内。

速度越快，内存占用越少越好，
看有没有两个都在O(n)尺度以内的算法。

问题背景：http://poj.grids.cn/practice/4036/

wayne

终于搞定了

平均的时间复杂度大致是 O(m)，(m<n) ,
空间复杂度 O(m).
http://poj.grids.cn/practice/4036/statistics/

gxqcn

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

wayne

3# gxqcn

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

1. #include <stdio.h>
   
2. #define MOD 10007
   
3. 
   
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. }
   
10. 
    
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.     }
    
36.    
    
37.     c=1 ;
    
38.     for(ii=0;ii<n;ii++)
    
39.     {
    
40.         c*=p[ii];
    
41.         c%=mod;
    
42.     }
    
43.     return c ;
    
44. }
    
45. 
    
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. }
    
52. 
    
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);
    
57.    
    
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);
    
67.    
    
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的乘积的模，还需要单独考虑