0830 commoncode 문서 원본 보기

$$ \frac{(a+b+c+\cdots+z)!}{a!b!c!\cdots z!} \pmod p \text{ where } p \text{ is a prime}$$

Above value is always integer. Refer [https://math.stackexchange.com/questions/2158/division-of-factorials the proofs]. The key observation is that the product of \(n\) consecutive integers is divisible by \(n!\).<ref> This can be proved by induction. [https://math.stackexchange.com/a/2171/64186]. And maybe possible by group theory</ref>
<pre>
p = int(1e9)+7 #example. this is a prime number
def anmodp(a, n): # a^n mod p 
    if n==1:
        return a%p

    tmp = anmodp(a, n/2)
    if n%2==1: #odd
        return (a*(tmp**2))%p
    else:
        return (tmp**2)%p 

def fac(n): # n! mod p 
    k = 1
    for i in range(2, n+1):
        k *= i
        k %= p
    return k

def invfac(n): # 1/(n!) (mod p)
    return anmodp(fac(n), p-2) #euler totient

def comb(x): # input = int array
    s = sum(x)
    ans = fac(s)
    for i in x:
        ans *= invfac(i)
    return ans % p
</pre>


<references/>

<disqus/>