前言

這一篇博客是在之前學(xué)習(xí)FFT的博客之后的，所以，如果你還不會FFT，請先看多項式乘法（FFT），在這篇博客里我有良心的詳細(xì)講解

正文

題型一：模板題&類模板題

• 模板系列可以供你檢測你寫的FFT是否正確，在很多OJ上都有
• 高精度系列，正式賽場上這樣的毒瘤題不是很多，現(xiàn)在的考題一般都會給一個模數(shù)讓你求，但是對于一些特殊的題可能還是會用到，所以可以練一練手（FFT可以優(yōu)化高精度乘法，高精度乘法優(yōu)化后可以優(yōu)化部分其它操作）

題型二：純卷積題

考慮一次多項式乘法$C=A?B$，其本質(zhì)是做一次普通的卷積
$$C_n=\sum _{i=1}^n{A}_i{B}_{n?i}$$
然后根據(jù)這個東西就能解決很多的問題

• 卷積推式子系列
  BZOJ3527，這一道題是一道典型的卷積題目，把推一下式子就直接搞定了
• 翻轉(zhuǎn)數(shù)組系列
  BZOJ2194這是一道裸題，可以練練手，很多題都會用到這類技巧

題型三：生成函數(shù)題

什么是生成函數(shù)？
$$g(x)=\sum _{i=0}^{\infty }f(i)?x^i$$
就是這樣一個東西，看起來好像很難的樣子，實際上也確實很難，對于一些各種各樣的$f(i)$推式子都很麻煩，但當(dāng)然也有簡單的題目（另外有非FFT的生成函數(shù)題，可以自行學(xué)習(xí)，如BZOJ3028）

• 在一些數(shù)中求選的數(shù)和的可能性系列
  BZOJ3771這一道題可以用容斥推一下式子，然后通過FFT來計算答案，方法就把指數(shù)當(dāng)成價值

題型四：匹配相關(guān)

• 特殊匹配系列
  BZOJ4503能匹配上代表0，把通配符視為0，求$(A_i?B_j{)}^2?A_i?B_j$即可
  常見模型：石頭剪刀布（分別標(biāo)值FFT）

題型五：結(jié)合其它數(shù)據(jù)結(jié)構(gòu)或者思想

BZOJ4332推公式+倍增

總結(jié)

FFT本身作為考點能考的東西并不是特別多，主要是考驗推式子的能力。由于我現(xiàn)在太菜，閱題不多，所以也不是很全，這篇博客將會持續(xù)更新

總結(jié)

以上是生活随笔為你收集整理的朴素多项式乘法考题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。