我在 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[] 中执行模运算以纠正此错误?
最佳答案
上述幂函数通过使用所谓的平方取幂计算 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) 变为偶数并且可以进行重复平方相同
更多信息请引用:
关于python - 关于模运算的行为?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21554556/