先简短几句话说说FFT....
多项式可用系数和点值表示，n个点可确定一个次数小于n的多项式。
多项式乘积为 f(x)*g(x)，显然若已知f(x), g(x)的点值，O(n)可求得多项式乘积的点值。
我们所需要的就是O(nlogn)快速地将两个系数多项式表示成点值多项式，O(n)求得乘积的点值表示后O(nlogn)还原成系数多项式。
这里就需要套FFT板子了...
FFT中取n个单位根，需要n是2的幂。
又因为n个点可确定一个次数小于n的多项式，所以n > 乘积多项式的最高次数。
以上。
HDU4609 n个木棍任取三根能组成三角形的概率。
数组开小莫名T,WA.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e5+;
struct comp{
double r,i;comp(double _r=,double _i=){r=_r;i=_i;}
comp operator+(const comp x){return comp(r+x.r,i+x.i);}
comp operator-(const comp x){return comp(r-x.r,i-x.i);}
comp operator*(const comp x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}
};
const double pi=acos(-1.0);
void FFT(comp a[],int n,int t){
for(int i=,j=;i<n-;i++){
for(int s=n;j^=s>>=,~j&s;);
if(i<j)swap(a[i],a[j]);
}
for(int d=;(<<d)<n;d++){
int m=<<d,m2=m<<;
double o=pi/m*t;comp _w(cos(o),sin(o));
for(int i=;i<n;i+=m2){
comp w(,);
for(int j=;j<m;j++){
comp &A=a[i+j+m],&B=a[i+j],t=w*A;
A=B-t;B=B+t;w=w*_w;
}
}
}
if(t==-)for(int i=;i<n;i++)a[i].r/=n;
}
comp x[N];
ll num[N], sum[N];
int main(){
int T; scanf("%d", &T);
while(T--){
memset(num, , sizeof num);
int n, u, maxnum = -; scanf("%d", &n);
for(int i = ; i < n; i++){
scanf("%d", &u);
maxnum = max(maxnum, u), num[u]++;
}
int len = ;
while(len <= maxnum*) len <<= ;
for(int i = ; i < len; i++)
x[i] = comp(num[i], );
FFT(x, len, );
for(int i = ; i < len; i++)
x[i] = x[i]*x[i];
FFT(x, len , -);
for(int i = ; i < len; i++)
sum[i] = x[i].r+0.5;
for(int i = ; i < len; i+=)
sum[i] -= num[i>>];//去掉两次取的木棍相同的
for(int i = ; i < len; i ++)
sum[i] >>= ;//算了2次
for(int i = ; i < len; i++)
sum[i] += sum[i-];
ll tot = (ll)n*(n-)*(n-)/, ans = tot;
for(int i = ; i <= maxnum; i++)
ans -= num[i]*sum[i];//去掉不能组成三角形的
printf("%.7f\n", 1.0*ans/tot);
}
return ;
}
LA4671 给出A串与B串，只含小写字母a、b。问：A串中有多少本质不同的子串满足 与B串长度相同 且 与B串相对应位置字符不同的数量小于k。
题解：a做1，b做0。将B倒着来一遍和A做卷积，可得有多少位置A串与B串都是a。a做0，b做1再来一遍即可。
hash！37做基1000173169做模会冲突！1e9+7做基1e9+9做模也会冲突！双哈希可以过，37做基2^64做模可过，37做基100000000173169LL做模也可过....
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N = 4e5+;
struct comp{
double r,i;comp(double _r=,double _i=){r=_r;i=_i;}
comp operator+(const comp x){return comp(r+x.r,i+x.i);}
comp operator-(const comp x){return comp(r-x.r,i-x.i);}
comp operator*(const comp x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}
};
const double pi=acos(-1.0);
void FFT(comp a[],int n,int t){
for(int i=,j=;i<n-;i++){
for(int s=n;j^=s>>=,~j&s;);
if(i<j)swap(a[i],a[j]);
}
for(int d=;(<<d)<n;d++){
int m=<<d,m2=m<<;
double o=pi/m*t;comp _w(cos(o),sin(o));
for(int i=;i<n;i+=m2){
comp w(,);
for(int j=;j<m;j++){
comp &A=a[i+j+m],&B=a[i+j],t=w*A;
A=B-t;B=B+t;w=w*_w;
}
}
}
if(t==-)for(int i=;i<n;i++)a[i].r/=n;
}
comp x[N], y[N];
char a[], b[];
int ans[N];
//hash
ull xp[] = {}, H[];
void initHash(){
H[] = a[];
for(int i = ; a[i]; i++)
H[i] = H[i-]*31uLL+a[i];
}
ull askHash(int l, int r){
if(l == ) return H[r];
return H[r]-H[l-]*xp[r-l+];
} int main(){
for(int i = ; i < ; i++) xp[i] = xp[i-]*31uLL; int ca = , K;
while(scanf("%d", &K), K != -){
scanf(" %s %s", a, b);
int lenA = strlen(a), lenB = strlen(b), len = ;
if(lenA < lenB){
printf("Case %d: %d\n", ca++, );
continue ;
} for(int i = ; i < lenB--i; i++)
swap(b[i], b[lenB--i]);
while(len <= lenA+lenB) len <<= ; for(int i = ; i < len; i++){
x[i] = comp(i < lenA? (a[i] == 'a'): , );
y[i] = comp(i < lenB? (b[i] == 'a'): , );
}
FFT(x, len, );
FFT(y, len, );
for(int i = ; i < len; i++)
x[i] = x[i]*y[i];
FFT(x, len, -);
for(int i = ; i < len; i++)
ans[i] = x[i].r+0.5; for(int i = ; i < len; i++){
x[i] = comp(i < lenA? (a[i] == 'b') : , );
y[i] = comp(i < lenB? (b[i] == 'b') : , );
}
FFT(x, len, );
FFT(y, len, );
for(int i = ; i < len; i++)
x[i] = x[i]*y[i];
FFT(x, len, -);
for(int i = ; i < len; i++)
ans[i] += x[i].r+0.5; initHash();
set<ull> se;
for(int i = lenB-; i < lenA; i++)
if(ans[i] >= lenB-K)
se.insert(askHash(i-lenB+, i));
printf("Case %d: %d\n", ca++, (int)se.size());
}
return ;
}
=================================分割线===================================
NTT
NTT与FFT类似，FFT用复数形式会有精度损失，而NTT则是在整数域内取模意义下，无精度损失。
如果 P = r⋅2k +1 是个素数，G是模P下的一个原根，那么在mod P 意义下，可以处理 2k 以内规模的数据 。
G在模P下的阶为 P-1，即 r⋅2k
那么Gr 在模P下的阶为2k ，这里的 Gr 即等价于FFT里的wn .
那么我们用模P下的卷积运算就不会产生精度损失。
P = 998244353 = 119*223+1, 能够处理223 = 8e6+ 规模的数据，原根为3.
P = 1004535809 = 479*221+1, 能够处理221 = 2e6+ 规模的数据，原根为3, 且 1004535809 加起来不会爆 int.
NTT能解决模数 P = r⋅2k +1 的问题，那么如何解决模任意数呢？
先前的 NTT资料 里有提到，
即用多个小素数跑NTT，最后用中国剩余定理求出 n(m-1)2 内满足条件的唯一值，当 各个素数积 > n(m-1)2 时中国剩余定理后显然可取得唯一值。
=================================分割线===================================
Ck = ∑i⊕j=k (Ai*Bj)， ⊕是某种运算符号。当⊕是+时，即是傅里叶变换；当⊕是^, &, |等某种位运算时，即是FWT快速沃尔什变换。
FFT中，数组长度要大于结果的最高次幂，高位补0；FWT时，数组长度需要是2的整数次幂，不足补0。
原理不是怎么重要...
模板套用即可。
//快速沃尔什变换
void FWT(int*a,int n){
for(int d=;d<n;d<<=)for(int m=d<<,i=;i<n;i+=m)for(int j=;j<d;j++){
int x=a[i+j],y=a[i+j+d];
//xor:a[i+j]=x+y,a[i+j+d]=x−y;
//and:a[i+j]=x+y;
//or:a[i+j+d]=x+y;
}
}
void UFWT(int*a,int n){
for(int d=;d<n;d<<=)for(int m=d<<,i=;i<n;i+=m)for(int j=;j<d;j++){
int x=a[i+j],y=a[i+j+d];
//xor:a[i+j]=(x+y)/2,a[i+j+d]=(x−y)/2;
//and:a[i+j]=x−y;
//or:a[i+j+d]=y−x;
}
}
防溢出可mod 1e9+7大质数，则除以2的时候乘2的逆元。
FWT后，相乘，UFWT回去即可。