Elementary combinatorics for 560E

Revision en2, by snsokolov, 2015-07-23 00:41:00

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English snsokolov 2015-07-23 00:41:00 26 Tiny change: ' and h celss is: \n\n' -
en1 English snsokolov 2015-07-23 00:36:39 678 Initial revision (published)