參考文章
FFT可以在nlogn的時間內實現n次多項式F(x)和m次多項式G(x)的卷積
$c_k={\sum }_{i+j=k}{a}_i{b}_j={\sum }_{i=0}^k{a}_i{b}_{k?i}$

基本形式：

對于類似：${\sum }_{i+j=N+k}{a}_i{b}_j$的式子，可以直接用FFT計算
例題：P3723 [AH2017/HNOI2017]禮物

直接計算卷積

經過簡單的推導即可推出可以用計算卷積來解決，這類問題多形如對所有不大于n的k求出某個東西，其中k的答案為求某個卷積后結果數組的第k項。

例題：CF993E

多項式運算

多項式乘法可以用來表示卷積，而借助多項式的性質，可以分析并解決類型更為廣泛的問題。其中，最典型的例子是利用生成函數解決組合計數問題，這往往可以簡化推導過程，有時還可以借助專用算法優化復雜度。

字符串匹配

設s,t為字符串，其中t中某些字符是通配符，可以匹配任意字符，求s在t中的所有匹配的位置。將通配符設為0，其余字符設為非0的數，則s在k處匹配當且僅當${\sum }_{0\le i<|s|}{t}_{i+k}(s_i?t_{i+k}{)}^2=0$
結合計算卷積，輕松算出左邊的式子，完成匹配
模板題：P4173 殘缺的字符串
CF528D Fuzzy Search

總結

以上是生活随笔為你收集整理的FFT的多种应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。