https://www.acmicpc.net/problem/31544 문제는 다음과 같다. 다음 문제를 하나의 생성함수로 나타내면 다음과 같다.$\begin{align} f(x)&=(\prod_{i=1}^{N} (1+x^i))^M \\&=a_0+a_1x^1+a_2x^2+a_3x^3+\cdots \end{align}$ 우리는 여기서 $\sum_{i=1}^{\infty} a_{Ki}$을 구해야 한다.이를 구하기 위해서 a root of unity를 사용할 것이다. $\zeta^K=1$인 a root of unity를 사용해보자.$\zeta^K=1$은 $\zeta^K-1=0$으로 바꾼 후 인수분해할 수 있다. $\zeta^K-1=(\zeta-1)(\zeta^{K-1}+\zeta^{K-2}+\cdots+\zeta..