Glucoco

题目链接：Codeforces 1238D

题目链接：Codeforces 86D

题目链接：ICPC 2019 上海网络赛B题

题目链接：HDU 6534

题目链接：BZOJ 2038

题目链接：Codeforce 1217E

题目链接：Codeforces 1217D

题目链接：ICPC 2019 徐州赛区网络赛 B

题目链接：ICPC 2019 徐州赛区网络赛 E

经典问题：记 $f(x)=\sum _{i=0}^n{a}_i{x}^i$，$g(x)=\sum _{i=0}^m{b}_i{x}^i$，其中$1\le n,m\le {10}^5$，求$f\cdot g(x)$。

显然如果我们做朴素的多项式乘法，时间复杂度是 $O(nm)$ 的。我们可以使用快速傅立叶变换（FFT）在 $O(c\log c)$ 的时间内解决此问题，其中 $c$ 是不小于 $n+m$ 的最小的 $2$ 的幂。

本文是笔者学习FFT的笔记和一些思考，不推荐作为教程食用。