https://en.wikipedia.org/wiki/Fast_Fourier_transform
多项式
n次多项式，n+1个系数
(a[0] + a[1] * x + a[2] * x^2 + .. + a[n] * x^n)
(b[0] + b[1] * x + b[2] * x^2 + .. + b[n] * x^n)
A * B = C
c[0] = a[0] * b[0]
c[1] = a[1] * b[0] + a[0] * b[1]
c[2] = a[2] * b[0] + a[1] * b[1] + a[0] * b[2]
...
暴力 O(n^2)
FFT O(n log n)
离散傅里叶变换
连续傅里叶变换（和我们做的比赛没什么关系）
复数
找到l个点，l是2的次幂，对2个多项式求值
通过一个算法 求值
A(0) == ..
A(1) == ..
..
A(l-1) == ..
B(0) == ..
B(1) == ..
..
B(l-1) == ..
对应的位置乘起来
C(0) == A(0) * B(0)
C(i) == A(i) * B(i)
..
根据
C(0) C(1) C(...)
推回多项式的系数
复数的乘法
模长相乘，幅角相加
2类
用复数 / 用double FFT
用数论 / 取模，用原根 NTT
a[0] + a[1] x + a[2] x^2 + a[3] x^3
w_n 是 n次单位根 (w_n)^n = 1 以下用 w
n = 4
w^n = 1
w^{n/2} = -1
b[0] = A(w^0) = a[0] * w^0 + a[1] * w^0 + a[2] * w^0 + a[3] * w^0
b[1] = A(w^1) = a[0] * w^0 + a[1] * w^1 + a[2] * w^2 + a[3] * w^3
b[2] = A(w^2) = a[0] * w^0 + a[1] * w^2 + a[2] * w^0 + a[3] * w^2
b[3] = A(w^3) = a[0] * w^0 + a[1] * w^3 + a[2] * w^2 + a[3] * w^1
a[0] = (b[0] * w^0 + b[1] * w^0 + b[2] * w^0 + b[3] * w^0) / 4
a[3] = (b[0] * w^0 + b[1] * w^1 + b[2] * w^2 + b[3] * w^3) / 4
a[2] = (b[0] * w^0 + b[1] * w^2 + b[2] * w^0 + b[3] * w^2) / 4
a[1] = (b[0] * w^0 + b[1] * w^3 + b[2] * w^2 + b[3] * w^1) / 4
a[0]
a[2]
a[1]
a[3]
a[0] * w^0 + a[2] * w^0
a[0] * w^0 + a[2] * w^2
a[1] * w^0 + a[3] * w^0
a[1] * w^0 + a[3] * w^2
a[0] * w^0 + a[2] * w^0 + a[1] * w^0 + a[3] * w^0
a[0] * w^0 + a[2] * w^2 + a[1] * w^1 + a[3] * w^3 = a'[1] + a'[3] * w
a[0] * w^0 + a[2] * w^0 + a[1] * w^2 + a[3] * w^2
a[0] * w^0 + a[2] * w^2 + a[1] * w^3 + a[3] * w^1 = a'[1] - a'[3] * w
n=8
A(w^0) = a[0] * w^0 + a[1] * w^0 + a[2] + a[3] + a[0]
A(w^1) = a[0] + a[1] * w + a[2] * w^2 + a[3] * w^3
A(w^2) = a[0] + a[1] * w^2 + a[2] + a[3] * w^2
A(w^3) = a[0] + a[1] * w^3 + a[2]^2 + a[3] * w
A(w^4) = a[0] + a[1] * w^3 + a[2]^2 + a[3] * w
A(w^5) = a[0] + a[1] * w^3 + a[2]^2 + a[3] * w
A(w^6) = a[0] + a[1] * w^3 + a[2]^2 + a[3] * w
A(w^7) = a[0] + a[1] * w^3 + a[2]^2 + a[3] * w
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
1 -> 001
4 -> 100
a[0]
a[4]
a[2]
a[6]
a[1]
a[5]
a[3]
a[7]
a[0] * w^0 + a[4] * w^0
a[0] * w^0 + a[4] * w^4
a[2] * w^0 + a[6] * w^0
a[2] * w^0 + a[6] * w^4
a[1] * w^0 + a[5] * w^0
a[1] * w^0 + a[5] * w^4
a[3] * w^0 + a[7] * w^0
a[3] * w^0 + a[7] * w^4
a' 表示上一组
a[0] * w^0 + a[4] * w^0 + a[2] * w^0 + a[6] * w^0 (a'[0] + a'[2] * w^0)
a[0] * w^0 + a[4] * w^4 + a[2] * w^2 + a[6] * w^6 (a'[1] + a'[3] * w^2)
a[0] * w^0 + a[4] * w^0 + a[2] * w^4 + a[6] * w^4 (a'[0] + a'[2] * w^4)
a[0] * w^0 + a[4] * w^4 + a[2] * w^4 + a[6] * w^2 (a'[1] + a'[3] * w^6)
http://lydsy.com/JudgeOnline/problem.php?id=3513
x^j的系数，是j在a数组中出现的次数
给定n个长度分别为a_i的木棒，问随机选择3个木棒能够拼成三角形的概率。
问概率 = 问方案数
全部 - 不能
不能 = (最大的 >= 较小的2个)
枚举最大的是谁，在所有中选取不同的2个，不考虑顺序，和小于等于最大的方案数
(.. x^j ..)^2 之后的 j 次方的系数就是从a数组中选取2个数字（考虑顺序，可以重复）和为j的方案数
http://www.51nod.com/Challenge/Problem.html#problemId=1030
高精度进制转换
bzoj 3160
万径人踪灭
bzoj 5217
航海舰队
bzoj 3992
序列统计
http://poj.openjudge.cn/campus2014/D/
Colorful World
n = 4
a[0] a[3] a[2] a[1]
a[1] a[0] a[3] a[2]
a[2] a[1] a[0] a[3]
a[3] a[2] a[1] a[0]
a[0] a[1] a[2] a[3]
p[0] p[1] p[2] p[3]
q[0] = a[0] * p[0]
q[1] = a[0] * p[1] + a[1] * p[0]
q[2] = a[0] * p[2] + a[1] * p[1] + a[2] * p[0]
q[3] = a[0] * p[3] + a[1] * p[2] + a[2] * p[1] + a[3] * p[0]
q[4] = a[1] * p[3] + a[2] * p[2] + a[3] * p[1]
q[5] = a[2] * p[3] + a[3] * p[2]
q[6] = a[3] * p[3]
q[0] = a[0] * p[0] + a[1] * p[3] + a[2] * p[2] + a[3] * p[1]
q[1] = a[0] * p[1] + a[1] * p[0] + a[2] * p[3] + a[3] * p[2]
q[2] = a[0] * p[2] + a[1] * p[1] + a[2] * p[0] + a[3] * p[3]
q[3] = a[0] * p[3] + a[1] * p[2] + a[2] * p[1] + a[3] * p[0]
经过
(1, 1) (2, 8) (3, 27) 的二次多项式是什么
x^3 % ((x-1)(x-2)(x-3)) 是什么？
https://www.codechef.com/problems/FARASA
数多少个不同的部分和，根据数据大小分类讨论
https://www.codechef.com/problems/COUNTARI
数i, j, k等差数列个数，分块FFT
https://www.codechef.com/problems/PRIMEDST
树上距离为质数的点对
https://www.spoj.com/problems/OVICUMSUM/
前缀和 FFT 组合数
luogu P5488
前缀和 FFT 组合数
A * B * C
FFT(A, 1)
FFT(B, 1)
AB = A * B
FFT(C, 1)
ABC = AB * C
FFT(ABC, -1)
FFT做多项式运算