Numbers Combination (BOJ 33104)

 

 

문제의 수식을 생성함수로 표현하면 다음과 같다.

\begin{align} f(x)&=\prod_{i=1}^n \sum_{j=1}^i x^j
\\ &=x^n(1+x)(1+x+x^2)\cdots(1+x+\cdots+x^{n-1})
\\ &=\frac{x^n(1-x)^n(1+x)(1+x+x^2)\cdots(1+x+\cdots+x^{n-1})}{(1-x)^n}
\\ &=x^n\cdot\prod_{i=1}^n \frac{1-x^i}{1-x}
\end{align}$

$$x^n$은 어짜피 계수가 1이므로 날리면 우리가 구해야 할 것은 $[x^{k-n}]$이 된다.
\begin{align} let\ g(x)&=\prod_{i=1}^n \frac{1-x^i}{1-x}
\end{align}$

\ e^{\ln g(x)}=g(x)$가 성립하므로, $ \ln g(x)$를 구해보고자 할 것이다.
\begin{align} \ln g(x)&=\ln \prod_{i=1}^n \frac{1-x^i}{1-x}
\\ &=\sum_{i=1}^n \{\ln(1-x^i) - \ln(1-x)\}
\\ &=\sum_{i=1}^n \ln(1-x^i)-n\ln(1-x)
\end{align}$

\ \ln(1-x^i)$를 어떻게 다항식꼴로 전개하면 좋을지 생각해보자.
\begin{align} \ln(1-x^i)=\int_{0}^{x^i} \frac{-ix^{i-1}}{1-x^i} dx \end{align}

\begin{align} let\ x^i=t,\ ix^{i-1}\cdot\frac{dx}{dt}=1,\ dx=\frac{dt}{ix^{i-1}} 
\end{align}
\begin{align}\int_{0}^{x^i} \frac{-ix^{i-1}}{1-x^i} dx&=\int_{0}^{t} \frac{-ix^{i-1}}{1-t}\cdot\frac{dt}{ix^{i-1}}
\\ &=-\int_{0}^{t} \frac{1}{1-t} dt
\\ &=-\int_{0}^{t} \sum_{j=0}^{\infty} t^j\ dt
\\ &=-\biggl[\sum_{j=0}^{\infty} \frac{1}{j+1}t^{j+1}\biggl]_{t=0}^{t=x^i}
\\ &=-\sum_{j\ge 1} \frac{1}{j}x^{ij}
\\ i\leftarrow1,\ n\ln(1-x)=\sum_{j\ge 1} \frac{n}{j}x^j
\end{align}
\begin{align} \ln g(x)&=\sum_{i=1}^n \ln(1-x^i)+\sum_{j\ge 1}\frac{n}{j}x^j
\\ &=-\sum_{i=1}^n \sum_{j>=1} \frac{n}{j}x^{ij}+\sum_{j\ge 1}\frac{n}{j}x^j
\\ &=\sum_{j\ge 1} (\frac{n}{j}x^j-\sum_{i=1}^n \frac{n}{j}x^{ij})
\\ &=\sum_{j\ge 1} (\frac{n}{j}x^j-\sum_{d|j,\ d\le n} \frac{1}{d}x^j) \ (\because Double\ Counting)
\end{align}$

\ \ln g(x)$는 $O(N log N)$안에 구할 수 있고, $\exp(\ln g(x))$도 $O(N log N)$ 안에 구할 수 있으므로 이제 $\ln g(x)$만 구해 https://www.acmicpc.net/problem/26037 처럼 풀면 된다.