๋ฌธ์
https://www.acmicpc.net/problem/11401
๋ฐฑ์ค ๋จ๊ณ๋ณ ํ์ด - ๋ถํ ์ ๋ณต
ํ์ด
์ดํญ๊ณ์๊ฐ ์ฃผ์ด์ก์ ๋, ์ดํญ๊ณ์ (N K)๋ฅผ 1,000,000,007๋ก ๋๋ ๋๋จธ์ง๋ฅผ ๊ตฌํด์ผํ๋ค.
์ดํญ๊ณ์๋ฅผ ๊ตฌํ๋ ๊ณต์์ nCk = n!/(k!(n-k)!) ๋ค.
์ ๋ฆฌํ๋ฉด ์๋์ ๊ฐ๋ค.
(n * (n-1) * (n-2) * (n-k+1) ์ฌ๊ธฐ๋ถํฐ (n-k)! * (n-k) * (n-k-1) * ... * 2 * 1)
/ (k * (k-1) * (k-2) * ... * 2 * 1)((n-k) * (n-k-1) * ... * 2 * 1)
=> (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 2 * 1)
๊ทธ๋ฆฌ๊ณ ์ด ๊ฐ๋ค์ 1,000,000,007๋ก ๋๋์ด์ค์ผํ๋ค.
์ด๊ฑธ ๋ถํ ์ ๋ณต์ผ๋ก ํ๋ ค๋ฉด ์ด๋ป๊ฒ ํ์ด์ผ ํ๋...๐ถ๐ซ
์ผ๋จ ํฉํ ๋ฆฌ์ผ์ ๊ตฌํ๋ ํจ์๋ฅผ ๋ง๋ค์ด์ ๋จ์๊ณ์ฐ ํ์์ผ๋ก ์ง๋ดค๋ค.
N, K = map(int, input().split())
namerge = 1000000007
def factorial(start, end):
ret = 1
for i in range(start, end+1):
ret *= i
return ret % namerge
print(factorial(N-K+1, N) // factorial(2, K) % namerge)
๊ฒฐ๊ณผ๋ ๋น์ฐํ ์๊ฐ ์ด๊ณผ๋ค.
๋๋๋๋ค๊ฐ ๊ฒฐ๊ตญ์ ๊ตฌ๊ธ๋ง...
์ฃผ์ด์ง ์๊ฐ๋ด์ ํต๊ณผํ๋ ค๋ฉด ๋ชจ๋๋ฌ ์ฐ์ฐ, ํ๋ฅด๋ง์ ์์ ๋ฆฌ ๊ฐ๋
์ ์ฌ์ฉํด์ผํ๋ค.
๋ชจ๋๋ฌ ์ฐ์ฐ
๋๋์
์ ๋๋จธ์ง๋ฅผ ๋ค๋ฃจ๋ ์ฐ์ฐ์ด๋ค.
a๋ฅผ m์ผ๋ก ๋๋ ๋๋จธ์ง์ b๋ฅผ m์ผ๋ก ๋๋ ๋๋จธ์ง๊ฐ ๊ฐ๋ค๊ณ ํ์๋,
$ a \equiv b (mod m) $ ์ผ๋ก ๋ํ๋ผ ์ ์๋ค.
๋ชจ๋๋ฌ ์ฐ์ฐ์ ๋ง์
, ๋บ์
, ๊ณฑ์
์ ๋ํด ๋ถ๋ฐฐ๋ฒ์น์ ์ฌ์ฉํ ์ ์๋ค.
ํํ๋ ๋ค์๊ณผ ๊ฐ๋ค.
๋ง์
: $ (A + B) mod C = (A mod C + B mod C) mod C $
๋บ์
: $ (A - B) mod C = (A mod C - B mod C) mod C $
๊ณฑ์
: $ (A * B) mod C = ((A mod C) * (B mod C)) mod C $
ํ์ง๋ง ์ดํญ๊ณ์๋ฅผ ๊ตฌํ๋ ๊ณต์์ ๋๋์
์ด๊ธฐ ๋๋ฌธ์, ๋ชจ๋๋ฌ ์ฐ์ฐ์ ์ฌ์ฉํ๋ ค๋ฉด ๊ณฑ์
ํํ๋ก ๋ณ๊ฒฝํด์ผํ๋ค.
์ดํญ๊ณ์๋ฅผ p๋ก ๋๋ ์์ ๊ณฑ์
ํํ๋ก ๋ณ๊ฒฝํ๋ฉด $ N! * (K! * (N-K)!)^{-1} mod p $ ๊ฐ ๋๋ค.
์ ๊ตณ์ด ๋ชจ๋๋ฌ ์ฐ์ฐ์ ์ฌ์ฉํด์ผ ํ๋๊ฐ?
=> $ N! * (K! * (N-K)!)^{-1} $๊ฐ ๋งค์ฐ ์ปค์ง์๋ ์๊ธฐ ๋๋ฌธ์ด๋ค.
์ด์ ์์ ์์ ๋ชจ๋๋ฌ ์ฐ์ฐ์ ์ ์ฉํ๋ฉด,
$ (N! mod p * ((N-K)!K!)^{-1} mod p) mod p $๊ฐ ๋ง๋ค์ด์ง๋ค.
ํ์ง๋ง -1์ ์ ๊ณฑํ๋ฉด ์ ์๊ฐ ์๋ ๊ฐ์ด ๋ง๋ค์ด์ง๋ฏ๋ก ์ ํ๋๊ฐ ๋จ์ด์ง๋ค.
-1์ ์์ ์ ์๊ฐ์ผ๋ก ๋์ฒดํ๊ธฐ ์ํด ํ๋ฅด๋ง์ ์์ ๋ฆฌ๊ฐ ํ์ํ๋ค.
ํ๋ฅด๋ง์ ์์ ๋ฆฌ
p๊ฐ ์์์ด๊ณ a๊ฐ p์ ๋ฐฐ์๊ฐ ์๋ ์ ์์ผ ๋, $ a^{p-1} \equiv 1 mod p $ ๊ฐ ์ฑ๋ฆฝํ๋ค.
(๋ฑํธ ์ธ๊ฐ๋ ํฉ๋์ด๋ผ๋ ์๋ฏธ๋ค. ํฉ๋์ '์ด๋ค ์ ์๋ก ๋๋ ๋๋จธ์ง๊ฐ ์๋ก ๊ฐ์ ๋ ์ ์ ์ฌ์ด์ ๊ด๊ณ'๋ฅผ ๋ปํ๋ค.)
์์ ์ ์๋ณ์ $ a^{-1} $ ์ ๊ณฑํด์ฃผ๋ฉด, $ a^{p-2} ≡ a^{-1} (mod p) $ ๊ฐ ๋๋ค!
์ฆ, ๋ชจ๋๋ฌ ์ฐ์ฐ์ ํตํด ๊ตฌํ ๊ฐ $ (N! mod p * ((N-K)!K!)^{-1} mod p) mod p $์
$ (N! mod p * ((N-K)!K!)^{p-2} mod p) mod p $๋ก ๋์ฒดํ ์ ์๊ฒ ๋๋ค.
์ ๋ต ์ฝ๋
N, K = map(int, input().split())
p = 1000000007
def factorial(n):
ret = 1
for i in range(2, n+1):
ret = (ret * i) % p
return ret
def square(n, k):
if k == 0:
return 1
ret = square(n, k//2)
if k % 2 == 0:
return (ret * ret) % p
else:
return (ret * ret * n) % p
top = factorial(N)
bottom = factorial(K) * factorial(N-K)
print(top * square(bottom, p-2) % p)
์์์ ๊ตฌํ๋ ์ $ (N! mod p * ((N-K)!K!)^{p-2} mod p) mod p $์ ๊ทธ๋๋ก ๊ตฌํด์ฃผ๋ ๋ฐฉ์์ด๋ค.
ํฉํ ๋ฆฌ์ผ ํจ์
def factorial(n):
ret = 1
for i in range(2, n+1):
ret = (ret * i) % p
return ret
์ฒซ ์๋์์ ์ฌ์ฉํ๋ ๊ณต์ (n * (n-1) * ... * (n-k+1)) / k!๋ฅผ ์จ๋จน์ด๋ ๋์ง๋ง,
์ ์งํ๊ฒ N!๊ณผ (N-K)!, K!๋ฅผ ๊ตฌํ๋ ๋ฐฉ์์ ์ฌ์ฉํ๋ค.
์ ๊ณฑ ํจ์
def square(n, k):
if k == 0:
return 1
ret = square(n, k//2)
if k % 2 == 0:
return (ret * ret) % p
else:
return (ret * ret * n) % p
์ ๊ณฑ ๋ฌธ์ ์์ ์ฌ์ฉํ๋ ๋ฐฉ์์ด๋ค.
์ง์๊ฐ ์ง์๋ผ๋ฉด square(n, k//2) * square(n, k//2)๋ฅผ, ํ์๋ผ๋ฉด n * square(n, k//2) * square(n, k//2)๋ฅผ ๋ฐํํ๋ค.
top = factorial(N)
bottom = factorial(K) * factorial(N-K)
print(top * square(bottom, p-2) % p)
top์๋ N!๋ฅผ, bottom์๋ (N-K)!K!๋ฅผ ํ ๋นํ๋ค.
๊ทธ๋ฆฌ๊ณ square(n, k)ํจ์๋ฅผ ํตํด ((N-K)!K!)^(p-2)๋ฅผ ๊ตฌํด์ค๋ค.
๋ง์ง๋ง์ผ๋ก ์ด ๋ ๊ฐ์ ๊ณฑํ ํ, p๋ก ๋๋๊ฐ์ ์ถ๋ ฅํ๋ฉด ๋์ด๋ค.
์ด๋ฐ ๋ฌธ์ ๋ค์ ๋ง๋ ๋๋ง๋ค ์ํ ๊ณต๋ถ์ ์ค์์ฑ์ ๋๋๋ค...^^
๋ฌธ์ ์ง์ ๋ค์ ์ด์๋ ์๊ณ ์ฐธ...