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

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

$$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 太強了