"0830 commoncode"의 두 판 사이의 차이
ph
(새 문서: $$ \frac{(a+b+c+\cdots+z)!}{a!b!c!\cdots z!} \pmod p$$ <pre> p = int(1e9)+7 def anmodp(a, n): if n==1: return a%p tmp = anmodp(a, n/2) if n%2==1: #odd re...) |
잔글 |
||
| (같은 사용자의 중간 판 4개는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
| − | $$ \frac{(a+b+c+\cdots+z)!}{a!b!c!\cdots z!} \pmod p$$ | + | $$ \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> | <pre> | ||
| − | p = int(1e9)+7 | + | p = int(1e9)+7 #example. this is a prime number |
| − | def anmodp(a, n): | + | def anmodp(a, n): # a^n mod p |
if n==1: | if n==1: | ||
return a%p | return a%p | ||
| 13번째 줄: | 14번째 줄: | ||
return (tmp**2)%p | return (tmp**2)%p | ||
| − | def fac(n): | + | def fac(n): # n! mod p |
k = 1 | k = 1 | ||
for i in range(2, n+1): | for i in range(2, n+1): | ||
| 20번째 줄: | 21번째 줄: | ||
return k | return k | ||
| − | def invfac(n): | + | def invfac(n): # 1/(n!) (mod p) |
return anmodp(fac(n), p-2) #euler totient | return anmodp(fac(n), p-2) #euler totient | ||
| − | def comb(x): # | + | def comb(x): # input = int array |
s = sum(x) | s = sum(x) | ||
ans = fac(s) | ans = fac(s) | ||
| 31번째 줄: | 32번째 줄: | ||
</pre> | </pre> | ||
| + | |||
| + | <references/> | ||
<disqus/> | <disqus/> | ||
2017년 8월 30일 (수) 22:47 기준 최신판
$$ \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 the proofs. The key observation is that the product of \(n\) consecutive integers is divisible by \(n!\).[1]
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