)
ωni 是一个单位根可以简单理解为 1xn1 的第 i 个解。由于虚数相乘就是长度相乘幅角相加所以单位根可以看作在一个单位圆分成的 n 等份每个在圆上对应的虚数。一次FFT操作我们可以得到至少 1n1 个点值表达以此来进行优化。我们假设我们要计算 s 个点值其中每个点对应的 xωsi 的话代入式子我们发现相隔一半总长的点也就是 ωsi 和 2ωsi2s 所对应的值只是奇数次项的符号不一样。这就是对称性了。那么我们就可以考虑把奇数位和偶数位给分开继续分治下去每次所需要处理的位置都是一半那么最后只有 loglogn 层这样就能在 (log)O(nlogn) 的时间复杂度内解决问题了。那么我们就能够快速得到这个多项式的 s 个点值了。然后考虑怎么才能够把这些点值重新变回多项式。这一部分也被称为快速傅里叶逆变换。推导过程比较复杂可以自己推。总而言之就是利用单位根的性质推导出结论。这边一般有两种处理方式我一般使用这种除了 00 的位置外其它位置翻转所有答案除以总长度。优化由于FFT需要大量三角函数、虚数、浮点数计算所以常数非常非常大所以往往需要一些卡常操作。第一个就是把分治操作改成迭代众所周知递归常数会比较大。第二个就是蝶形运算优化这一优化的意义在于我们每次会把奇数位和偶数位拆开然后合并非常麻烦蝴蝶优化帮我们提前把位置分配好了那么我们就不需要再去进行复杂的操作了。代码实现其实看别人推导一遍还是很容易的但是自己考场上也不可能去推那么就直接记住板子怎么敲吧。只要知道每一步都在干嘛还是很好记的。代码以HDU - 4609为例cpp#includebits/stdc.h #define int long long using namespace std; const double Piacos(-1); int T,n,a[400005],id[400005],c[400005]; complexdouble d[400005]; void FFT(complexdouble *a,int n,int op){ for(int i0;in;i)if(id[i]i)swap(a[id[i]],a[i]); for(int len2;lenn;len1){ complexdouble W(cos(2*Pi/len),sin(2*Pi/len)),w0(1,0); for(int l0;ln;llen){ complexdouble ww0; for(int il;il(len1);i,ww*W){ auto xa[i],ya[i(len1)]*w; a[i]xy,a[i(len1)]x-y; } } } if(op-1){ reverse(a1,an); for(int i0;in;i)a[i]/n; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); cinT; while(T--){ cinn; int ma0; for(int i1;in;i)cina[i],d[a[i]]1.0,mamax(ma,a[i]); int s1,l0; while(s(ma1))s1,l; for(int i0;is;i)id[i](id[i1]1)|((i1)l-1); FFT(d,s,1); for(int i0;is;i)d[i]*d[i]; FFT(d,s,-1); for(int i0;is;i)c[i](int)(d[i].real()0.5); for(int i1;in;i)c[a[i]*2]--; for(int i0;is;i)c[i]1; for(int i1;is;i)c[i]c[i-1]; int ans0,sum0; for(int i1;in;i){ sum(i-1)*(i-2)/2; ansc[a[i]]; } for(int i0;is;i)c[i]0,d[i]complexdouble(0,0); for(int i0;ima;i)a[i]0; anssum-ans; coutfixedsetprecision(7)(1.0*ans/sum)endl; } return 0; }数论变换NTT整体思想NTT 的整体思想和 FFT 是一致的唯一区别是 NTT 使用了原根代替单位根。这明显是有前提的就是要有模数否则也不会有原根。假设原根为 g模数为 P那么需要满足 (−1)modgn(P−1)imodP 的结果两两不同。通常来讲常见的原根是 33最常见的模数就是经典常数 998244353998244353。然后我们把 gi 代入每一个点值表达代替 FFT 的单位根就可以得到一样的结果了。代码实现代码以洛谷 - P4721为例cpp#includebits/stdc.h #define int long long using namespace std; const int mod998244353; int n,g[400005],f[400005],id[400005],tmp[400005],tmp2[400005]; int ksm(int a,int b){ int s1,xa; while(b){ if(b1)ss*x%mod; xx*x%mod; b1; } return s; } void NTT(int *a,int n,int op){ for(int i0;in;i)if(id[i]i)swap(a[id[i]],a[i]); for(int len2;lenn;len1){ int Wksm(3,(mod-1)/len); for(int l0;ln;llen){ int w01; for(int il;il(len1);i,w0w0*W%mod){ int xa[i],ya[i(len1)]*w0%mod; a[i](xy)%mod,a[i(len1)](x-ymod)%mod; } } } if(op-1){ reverse(a1,an); int invksm(n,mod-2); for(int i0;in;i)a[i]a[i]*inv%mod; } } void solve(int l,int r){ if(lr)return;
