[BOJ 13178] 목공

$$a_n = \sum_{i=1}^{N} a_{n-i} C_i + 1$$

위 점화식을 만족하는 수열 $a_n$을 $N\le 16000$, $n \le 10^{12}$ 범위에서 계산해야 한다. (표기에서 문제의 $M$와 $n$을 혼용함)

$$a_n = \sum_{i=1}^{N} a_{n-i} C_i$$

위 점화식을 만족하는 수열 $a_n$의 경우 키타사마법을 이용하되 FFT를 이용한 $O(NlogN)$ 시간 곱셈/나눗셈을 하면 $O(NlogNlogM)$만에 계산할 수 있다.

상수항을 구현하기 위해 $a_n$ 대신 $a_n=b_n-kn$을 넣어주면 상수항을 쉽게 없앨 수 있다.

일반항을 구하는 관점에서는 $a_n= \sum r_i^n$ 대신(얘는 상수항이 걸려서 점화식 만족이 안된다) $a_n=\sum r_i^n + kn$을 채택하여 $k$를 적당히 조정하여 점화식을 만족시키는 거라고 볼 수 있다.

참고로 $a_n=\sum r_i^n +k$는 아무 쓸모 없다. 보통은 쓸모가 있었을텐데 이 문제의 경우 특수하게 계수의 합 $\sum C_i=1$이어서, $k(\sum C_i -1)=1$이 되어 $k$를 어떻게 정하든 방정식을 만족시키지 못하고 상수항을 못 없앤다.