在学各种数各种反演之前把以前做的$FFT$/$NTT$的题整理一遍

还请数论$dalao$口下留情

题目中要求求出

$c_k=sumlimits_{i=k}^{n-1}a_i*b_{i-k}$

首先可以把$a$翻转,

$c_k=sumlimits_{i=k}^{n-1}a_{n-1-i}*b_{i-k}$

$c_k=sumlimits_{i=0}^{n-k-1}a_{n-k-1-i}*b_{i}$

$f[i]=sum_{j=1}^{i-1}frac{q[j]}{(i-j)^2}-sum_{j=i+1}^{n}frac{q[j]}{(i-j)^2}$

$f[i]=sum_{k=1}^{min(n-i,i-1)}frac{q[j-k]-q[j+k]}{k^2}$

构造出一个$g[i]=frac{1}{i^2}$就是一个裸的卷积了

T4Triple

这道题的FFT并不难想，只是容斥比较复杂，在这里不再赘述

T5万径人踪灭

设$c[i]=sumlimits_{j=1}^{i-1}[s[i]==s[i-j]]$($s$数组从$1$开始编号)

$ans_i=2^{c[i]}$-不合法的个数，不合法的可以用$hash$二分

求$c[i]$可以分别考虑$a$,$b$的贡献，以a为例：设$b[i]=s[i]=='a'$

那么$c[i]=sumlimits_{j=1}^{i-1}b[j]*b[i-j]$，便成了卷积的形式，FFT求解即可

看到乘积果断选择原根化乘法为加法，之后因为N很大，需要用快速幂+NTT