python - 关于模运算的行为？

Question

我在 python 中针对以下 codechef 问题编写了以下程序 http://www.codechef.com/problems/MOVES/

import sys

tokenizedInput = sys.stdin.read().split()
mod=1000000007
arr=[1]*5001
for i in range(1,5001):
    arr[i]=(arr[i-1]*i)%mod

def combo(r,n,mod):
    q=arr[n]
    print q
    r=(arr[r]*arr[n-r])
    print r
    return ((q/r)%mod)

elm=0

for i in range (0,5001):
    n=int(tokenizedInput[elm])
    elm=elm+1
    k=int(tokenizedInput[elm])
    elm=elm+1
    if(n==0 and k==0):
        break
    out=0
    if(((k-1)/2)!=(k/2)):
      out=(2*combo((k-1)/2,n-2,mod)*combo(k/2,n-2,mod))%mod
    else:
      out=(2*combo(k/2,n-2,mod)**2)%mod
    print out

但我的取模函数无法正常工作，例如对于值 n=498并且 r=2 combo() 返回的答案是 0 因为 q=243293343 和 r=1428355228如何在 arr[] 中执行模运算以纠正此错误？

Answer 1

上述幂函数通过使用所谓的平方取幂计算 O( log(b) ) 中的 a^b。这个想法很简单:

       (a^2)^(b/2)          if b is even and b > 0
a^b =  a*(a^2)^((b-1)/2)    if b is odd
        1                  if b = 0

这个想法可以很容易地实现，如下所示:

/* This function calculates (a^b)%c */
int modulo(int a,int b,int c)
{
    long long x=1,y=a; 
    while(b > 0)
    {
        if(b%2 == 1)
        {
            x=(x*y)%c;
        }
        y = (y*y)%c; // squaring the base
        b /= 2;
    }
    return x%c;
}

上面的幂函数只是一种递归的方法。正如你所问的那样

but it will be of great help if anyone explains the mathematics behind using return(base*Power(base,expo-1)%mod)

这与检查 expo 是否为奇数然后将 base 与 base^(expo-1) 相乘以使新的 expo 即 (expo-1) 变为偶数并且可以进行重复平方相同

更多信息请引用:

Topcoder Tutorial

wiki: expo by squaring