• HDU 4609 3-idiots
  题目链接
  题解
  这个题考察了如何转化成多项式乘法，然后去重和计数很有意思
• HDU 1402 A*B problem plus
  题目链接
  将整数转化成向量，最后得到的卷积后的向量处理一下每一位的进位就是结果
• BZOJ 2194 快速傅立叶之二
  题目链接
  FFT 能解决形如 c[k] =sigma(a[p]*b[k-p]) (0<=p<=k) 的式子，如果是c[k] = sigma(a[p],b[p+k]),可以将其中一个向量倒过来，这样就变成第一种情况了，当然所求的下标也变化了
• BZOJ 3527 力
  题目链接
  公式推导
  和BZOJ2194类似，我们要将原式转化成c[k] =sigma(a[p]*b[k-p]) (0<=p<=k) ， 熟练运用换元法、缩放和向量转置，得到满足卷积条件的表达式
• BZOJ 3771 Triple
  题目链接
  容斥分析
  这道题考点在于是否了解DFT、IDFT之后求的是什么东西，只要心里清楚，就很容易做了

什么是卷积

参考资料1
参考资料2

多项式乘法就是求卷积
1 3 3 4
把这个数组转化成num数组，num[i]表示数字i的有num[i]个。
num = {0 1 0 2 1}
代表0的有0个，1有1个，2有0个，3有2个，4有1个。
使用FFT解决的问题就是num数组和num数组卷积。
num数组和num数组卷积的解决，其实就是从{1 3 3 4}取一个数，从{1 3 3 4}再取一个数，他们的和每个值各有多少个
例如：
{0 1 0 2 1}{0 1 0 2 1} 卷积的结果应该是{0 0 1 0 4 2 4 4 1 }
长度为n的数组和长度为m的数组卷积，结果是长度为n+m-1的数组。
{0 1 0 2 1}{0 1 0 2 1} 卷积的结果应该是{0 0 1 0 4 2 4 4 1 }。
这个结果的意义如下：
从{1 3 3 4}取一个数，从{1 3 3 4}再取一个数
取两个数和为 2 的取法是一种：1+1
和为 4 的取法有四种：1+3， 1+3 ，3+1 ，3+1
和为 5 的取法有两种：1+4 ，4+1；
和为 6的取法有四种：3+3,3+3,3+3,3+3,3+3
和为 7 的取法有四种： 3+4,3+4,4+3,4+3
和为 8 的取法有 一种：4+4

关于多项式

• 次数界：对于多项式A(x)，系数为ai,设最高非零系数为ak，任何大于k的整数都是A(x)的次数界
• 系数表达式：
• 系数向量：a=(a0,a1,...,an−1)
• 点值表达方式：{(x0,y0),(x1,y1),...,(xn−1,yn−1)} ，其中xk各不相同，yk=A(xk)

快速傅立叶变换（FFT）

快速计算DFT（离散傅里叶变换）的算法
时间复杂度：O(nlogn)

复数

const double pi = acos(-1);
const double pi_2 = 2*pi;
struct Complex // 复数
{
    double r, i;
    Complex(double _r = 0, double _i = 0) :r(_r), i(_i) {}
    Complex operator +(const Complex &b) {
        return Complex(r + b.r, i + b.i);
    }
    Complex operator -(const Complex &b) {
        return Complex(r - b.r, i - b.i);
    }
    Complex operator *(const Complex &b) {
        return Complex(r*b.r - i*b.i, r*b.i + i*b.r);
    }
};

FFT模板

• 非递归

void func1(Complex pos[],int n){
    int j = __builtin_ctz(n)-1;
    for(int i=0;i>1]>>1 | ((i&1)<

while(len