__water

多项式有两种表达，一种是系数表达式，一种是点值表达式。 转自iamzky 可以看出时间复杂度从n^2变成了n 于是我们得到一个计算多项式的方法： n次单位复数根 使用单位根计算点值表达式叫DFT（离散傅里叶变换）复杂度n^2，FFT是其优化版复杂度nlogn

FFT是计算卷积的，就是 FFT大数乘法模版：#include<cstdio> #include<cmath> #include<cstring> #include<algorithm>using namespace std; const int N = 500005; const double pi = acos(-1.0);char s1[N],s2[N]; int len,res[N]

先用NTT求出两两组合的方案数 然后就能o(n) 求出能组成三角形的方案数 NTT:#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+10; const ll mod=( 1ll << 47 ) * 7 * 4451 + 1 ; const ll g=3; ll mul( ll