0830 commoncode - 편집 역사

2017년 8월 30일 (수) 13:47에 Admin님의 편집

2017-08-30T13:47:31Z

2017년 8월 30일 (수) 13:47에 Admin님의 편집

2017-08-30T13:47:04Z

2017년 8월 30일 (수) 13:44에 Admin님의 편집

2017-08-30T13:44:35Z

2017년 8월 30일 (수) 08:56에 Admin님의 편집

2017-08-30T08:56:48Z

2017년 8월 30일 (수) 08:54에 Admin님의 편집

2017-08-30T08:54:09Z

Admin: 새 문서: $$ \frac{(a+b+c+\cdots+z)!}{a!b!c!\cdots z!} \pmod p$$

 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...

2017-08-30T08:52:26Z

새 문서: $$ \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...

새 문서

$$ \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
return (a*(tmp**2))%p
else:
return (tmp**2)%p

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

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

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

<disqus/>

@@ 1번째 줄: / 1번째 줄: @@
 $$ \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 using group theory</ref>
+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

← 이전 판		2017년 8월 30일 (수) 13:47 판
32번째 줄:		32번째 줄:
	</pre>		</pre>

		+
		+	<references/>

	<disqus/>		<disqus/>

@@ 1번째 줄: / 1번째 줄: @@
 $$ \frac{(a+b+c+\cdots+z)!}{a!b!c!\cdots z!} \pmod p \text{ where } p \text{ is a prime}$$
 <pre>
 p = int(1e9)+7 #example. this is a prime number

@@ 3번째 줄: / 3번째 줄: @@
 <pre>
 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:
          return a%p
@@ 13번째 줄: / 13번째 줄: @@
          return (tmp**2)%p
-def fac(n):
+def fac(n): # n! mod p
      k = 1
      for i in range(2, n+1):
@@ 20번째 줄: / 20번째 줄: @@
      return k
-def invfac(n):
+def invfac(n): # 1/(n!) (mod p)
      return anmodp(fac(n), p-2) #euler totient
-def comb(x): # arr
+def comb(x): # input = int array
      s = sum(x)
      ans = fac(s)