组合数的模运算

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;
17. return s;
18. }
19. }
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);
28. if(x_k<0) x_k+=mod;
29. return (tmp_k*x_k)%mod;
30. }

复制代码