относительно поведения операции по модулю?

Я написал следующую программу на 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 [], чтобы исправить эту ошибку ?

3 3
python modulus

3 ответа:

Когда мы делим (a/b)%MOD, то делаем что-то вроде этого .

(a/b)%MOD

(a * inverse (b))%MOD // вы должны найти обратную b. чтобы найти обратную b, используйте теорему Ферма.

Примечание никогда не делите a/b, а затем возьмите MOD, сначала найдите обратное b, а затем сделайте a*b, а затем МОДУЛИРУЙТЕ его .

0

Приведенная выше степенная функция вычисляет a^b в O (log (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;
}
Приведенная выше степенная функция - это просто рекурсивный способ сделать это. и как вы спросили об этом

Но будет очень полезно, если кто-нибудь объяснит математику использования return (base * Power(base, expo-1)%mod)

Это то же самое, что проверка нечетности expo затем умножение базы на базу^(expo-1) так, чтобы новая expo т. е. (expo-1) стала четной и повторное возведение в квадрат может быть сделано

Для получения дополнительной информации см.:

Учебник По Topcoder

Wiki: expo by squaring

1

Получил решение, отвечая на мой собственный вопрос , но поиск оптимизированной версии поощряется ошибка была

Return ((q/r)%mod)

Неверно для mod, являющегося 1000000007, то есть простым числом, оно должно быть записано как

R=(arr[r]*arr[n-r])%mod

Return (q * Power (r, mod-2))%mod

Где степенная функция равна 

def Power(base,expo):
if(expo==0):
  return 1
else:
    if(expo&1):
      return(base*Power(base,expo-1)%mod)
    else:
      root=Power(base,expo>>1)
      return(root*root%mod)

Но будет очень полезно, если кто-нибудь объяснит математику, стоящую за использованием return (base * Power (base, expo-1) % mod)

0