洛谷 P5224 - Candies（循環卷積）

循環卷積+NTT

​​洛谷題面傳送門​​

一道題解長度大概不到 1k 的題，可還是決定寫篇題解，因為自己沒有做出來（

\(1004535809\) 好評（

首先這個 \(\equiv m\pmod{k}\) 有點把我們往機關根反演的方向思考的意思，不過注意到 \(k\) 不一定是 \(1004535808\) 的約數，是以在多數情況下 \(k\) 次機關根是不存在的，是以我們隻能放棄這個想法。

然後我便想着如何裂組合數，發現裂了之後還要再裂，如此不停遞歸下去，進而獲得了複雜度優秀的 \(\mathcal O(nk)\) 的做法。看了題解才發現自己是多麼 sb……

注意到這個組合數很容易讓我們與二項式産生聯想，具體來說 \(\dbinom{n}{i}=[x^i](1+x)^n\)，而比較巧的一點是我們求和的組合數中所有組合數的上部都是相同的，也就是說答案就是 \((1+x)^n\) 中所有次數 \(\bmod k=m\) 的項的系數之和。看到次數 \(\bmod k\) 又能讓我們發生怎樣的聯想呢？……循環卷積！我們考慮求 \((1+x)^n\) 時，對次數做 \(\bmod k\) 意義下的循環卷積，這樣最終答案就是求得的長度為 \(k\) 的多項式中，\(x^m\) 前的系數。注意到 NTT 是可以解決循環卷積問題的，是以 NTT+循環卷積即可。

又幫我複習了一個 9 個月前學的東西（bushi，因為這東西大概 3 個月後還要再次學到）