[CodeUp/3726] 답이 없는 조합론 문제 (Python)

Problem : 답이 없는 조합론 문제 (codeup.kr)

Status : Solved

Time : 00:37:26

 

---

 

문제 설명

 

조합론에 관련된 문제를 출제하고 싶었지만, 적절한 난이도의 조합론 문제를 출제하는데 어려움을 겪은 hi12는
자신의 친한 친구인 bye17에게 조합론 관련된 문제를 추천해달라는 메일을 보냈다.

잠시 후, bye17은 다음 문제를 추천해줬다.

$$ \sum_{n=0}^{X} \left ( \sum_{r=0}^{n} ( _{n}C_{r} )^2 ) \right ) $$

X는 최대 300,000 이고,
수가 매우 커질 수 있으니 99824353으로 나눈 나머지를 출력하면 되는 문제야.
참고로, 99824353은 소수야.

hi12는 이 문제가 마음에 들었고, 이대로 문제를 출제하려 했지만
풀이를 작성하던 도중, X의 범위 때문에 시간 초과가 난다는 사실을 알아차렸다.
hi12는 bye17에게 풀이를 알려달라고 했지만, 답장이 오지를 않자
당신에게 코드를 대신 짜달라고 부탁해왔다.

hi12를 대신해 저 문제를 풀어주자.

 

입력 및 출력

 

입력

첫 번째 줄에 정수 X가 주어진다. (0 ≤ X ≤ 300,000)

출력

위 식의 답을 99,824,353으로 나눈 나머지를 출력한다.

 

입력 예시

2

출력 예시

9

 

---

 

풀이

 

우선, 조합론의 성질을 고려해보도록 하자. 고등 수학 조합론에서는 다음 식이 성립함을 알 수 있다.

$$ \sum_{r=0}^{n} ( _{n}C_{r} )^2 = _{2n}C_{n} $$

 

또한, bn = 2nCn은 다음과 같은 공비가 적용되는 공비수열이다.

$$ \frac{_{2n}C_{n}}{_{2(n-1)}C_{n-1}} = \frac{(2n)!}{n!n!} \cdot \frac{(n-1)!(n-1)!}{(2n-2)!} = \frac{4n-2}{n} $$

 

따라서, 각 항을 차례대로 공비를 곱해가며, 그 결과를 더해 주면 전체 제곱의 합을 구할  수 있다. 문제는 모듈로 연산을 포함할 때, 나눗셈은 지원하지 않는다. 모듈러 연산의 역원과 페르마의 소정리를 구해 주어야 한다. 자세한 정리는 나중에 하기로 하고, 그 결과는 이렇다 : (이 때 모듈러 연산의 m이 소수여야만 성립한다)

$$ a^{-1} mod \; m = a^{mod-2} mod \; m $$

 

이 때, mod-2는 매우 큰 수이므로 이러한 제곱 연산 역시 최적화해주어야 한다. 앞선 문제에서도 이러한 제곱 연산을 줄이는 코드를 다룬 바 있다.

2022.11.29 - [알고리즘 문제/CodeUp] - [CodeUp/2753] 수열의 n번째 항 (Python)

[CodeUp/2753] 수열의 n번째 항 (Python)

 

이 세 가지 경우를 고려한 풀이는 다음과 같아진다.

처음엔 모듈러 연산 역원을 고려하지 않아서 맞왜틀만 외치고다녔는데... 바로 떠올리는 습관이 필요하다!

 

풀이 코드

def pow(n, k):
  if k == 0 :
    return 1
  if k ==  1 :
    return n

  _n = (pow(n, k//2)) % MOD
  _n = (_n*_n) % MOD
  if k % 2 == 0:
    return _n
  else :
    return (_n * n) % MOD
  

MOD = 99824353
x = int(input())

result = 1
tot_sum = 1

for i in range(1, x+1) :
  result = (result *(4*i-2)) % MOD
  mod_inv = pow(i, MOD - 2) % MOD
  result = (result*mod_inv) % MOD
  tot_sum = (result + tot_sum) % MOD

print(tot_sum)

 

풀이 완료!