Блог пользователя snsokolov

Автор snsokolov, история, 9 лет назад, По-английски

For the http://mirror.codeforces.com/contest/560/problem/E

Number of distinct ways (only Down and Right) modulo p in a grid of w and h cells is:

modC(w+h-2, h-1, p) , where

modC(n, k, p) = C(n, k) mod p = modFact(n, p) * ((modInvFact(k, p) * modInvFact(n-k, p) mod p) mod p

modFact(n+1, p) = modFact(n, p) * (n+1) mod p, where modFact(0, p) = 1

modInvFact(n-1, p) = modInvFact(n, p) * n mod p, where modInvFact(N, p) = modExp(modFact(N, p), p-2, p)

modExp(n, e, p):
    res = 1
    b = n mod p
    while e > 0
        if (e mod 2 == 1):
           res := (res * b) mod p
        e >>= 1
        b = (b * b) mod p
    return res
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится