題目可以寫成多項式的形式，其中次方代表飽足度，係數代表這個飽足度的數量

範例測資一就可以寫成以下的形式

$$P(x) = 1 + x + x^2$$

第 $N$ 天各種飽足度的數量就是 $P^N(x)$

這個要怎麼計算呢？用 $\text{FFT/NTT}$ 可以 $O(K \cdot \log(K) \cdot \log(MOD))$ 內計算，但這只能拿到 $\text{82%}$

我們可以整理算式！

$$Ans = P^N(x)$$

$$\ln(Ans) = \ln(P^N(x)) = N \cdot \ln(P(x))$$

$$e^{ln(Ans)} = e^{N \cdot \ln(P(x))}$$

$$Ans = e^{N \cdot \ln(P(x))}$$

那答案就是 $e^{N \cdot \ln(P(x))}$，可以在 $O(K \log(K))$ 內計算，簡直好到不真實！

窩心裡只有兩個字：becaidorz 太強了