BOJ 2500 : 복불복

https://www.acmicpc.net/problem/2500

2500번: 복불복

상당히 어렵고 재밌는 발상의 문제이다.

 

회전판을 한 번 돌렸을 때 i개의 돌을 가져갈 때의 가능한 경우의 수를 C_i라고 하면

C_0 + C_1*x + C_2*x^2 + ........ C_k*x^k 라는 다항식을 만들 수 있다.

 

이때 x^i에서의 i는 쓴 돌의 갯수라고 생각하면 이해가 편하다.

 

그렇다면 N번 회전판을 돌렸을때는 이렇게 표현할 수 있다.

(C_0 + C_1*x + C_2*x^2 + ........ C_k*x^k)^N = A_0 + A_1*x + A_2*x^2 + .......... A_(Nk)*x^(Nk)

 

저 식을 통해 N번 회전판을 돌렸을 때 가능한 모든 경우의 수는  Σ(A_i)(0<=i<=N*k)임을 알 수 있다.

그러나 우리는 N번 회전판을 돌리고 나서 0개 이상의 돌이 있어야 하기 때문에 N번 회전판을 돌렸을 때 i개(0<=i<=k)가 남는 경우의 수를 구해야 한다.

 

전에 말했듯이, x^i에서의 i는 쓴 돌의 갯수라고 생각하면 우리가 구하고자 하는 것은 Σ(A_i)(0<=i<=k)임을 알 수 있다.

 

이를 Naive하게 구하면 O(NK^2)이고, 이는 아직 문제를 풀기엔 너무 느리다.

 

그렇다면 ^N을 분할 정복을 이용하여 log N만에 하게끔 최적화를 시키면, O(K^2 log N)으로 문제가 풀린다.

 

코드