组合数的模运算

wayne

7# mathe

mathe可以看一下 原题，我已经追加在主题帖里了

gxqcn

固定数做除数，是有特殊加速算法的，可以用乘以一个固定数再右移固定位数即可，以避免除法指令。

wayne

6# wayne

这题竟然被我蒙混过关了

准确的说，不是蒙混过关，而是代码很dirty，函数模块封装的不好。
应该在powMod(a,n,MOD);的里面 做 a%=MOD

wayne

12# gxqcn
哦，不解。“固定数取模” 就是 我前面说的两个数的乘积的取模吗，
老大可否再透露一点细节，
俺对大数运算，高精度计算，符号运算 还是很感兴趣的，
虽然如此，但一直没有花时间去深入的编程实践，积攒甚少。

gxqcn

刚才有点“笔误”，我说的是常数作被除数时有快速算法：


Unsigned division by constant
=============================

enter divisor: 10007

; dividend: register other than EAX or memory location

MOV EAX, 0x68C8C4AD
MUL dividend
SHR EDX, 12

; quotient now in EDX

IMUL EDX, 10007
SUB EAX, EDX

; remainder now in EAX

wayne

汇编呀，

mathe

对于M是素数还是比较简单的。先计算分子分母中M次数是否相等，如果不等答案就是0
然后分子分母分别模M相乘，但是遇上M的倍数要先将M因子全除去（而这里由于M已知，不需要每个数都判断，而是可以写成两重循环）。于是得到结果a/b(mod M)，
然后对b求数论倒数相乘即可。

mathe

divid by constant优化通常编译器自己会做

wayne

17# mathe
多谢mathe！
简直是 高屋建瓴，势如破竹啊

wayne

得空 按mathe的思路实现出来了：

1. int extendedGCD(int a, int b, int &x, int &y)
   
2. {
   
3.     /*ax+by=gcd(a,b)*/
   
4.     if(b==0)
   
5.     {
   
6.         x=1;
   
7.         y=0;
   
8.         return a;
   
9.     }
   
10.     else
    
11.     {
    
12.         int s = extendedGCD(b,a%b,x,y);
    
13.         int tmp=x;
    
14.         x=y;
    
15.         y=tmp-(a/b)*y;
    
16. 
    
17.         return s;
    
18.     }
    
19. }
    
20. 
    
21. int binomialMod(int k,int n,int mod)
    
22. {
    
23.     int ii,tmp_k=1,tmp_n=1,g,x_k,y_mod;
    
24.     for(ii=0; ii<n; ii++) tmp_k*=k-ii,tmp_k%=mod;
    
25.     for(ii=1; ii<=n; ii++) tmp_n*=ii,tmp_n%=mod;
    
26.     g=extendedGCD(tmp_n,mod,x_k,y_mod);
    
27. 
    
28.     if(x_k<0) x_k+=mod;
    
29.     return (tmp_k*x_k)%mod;
    
30. }

复制代码