FFT解决高精度乘法
众所周知，FFT是用来做多项式乘法的，很多同学都知道可以用于高精度乘法，但是高精度乘法和FFT怎么联系起来的？
举例来说，计算\(123*456\)，可以把\(123\)和\(456\)看成是\(100+20+3\)和\(400+50+6\)，然后\((100+20+3)(400+50+6)=1*100*4*100+1*100*5*10+1*100*6*1+2*10*4*100+2*10*5*10+2*10*6*1+3*1*4*100+3*1*5*10+3*1*6*1=4*10000+(5+8)*1000+(6+10+12)*100+(12+15)*10+18*1=56088\)
多项式乘法是对于\(f(x)=\sum\limits_{i=0}^nf_ix^i=1*x^2+2*x^1+3*x^0\)和\(g(x)=\sum\limits_{i=0}^{m-1} g_i x^i=4*x^2+5*x^3+6*x^0\)
计算两个多项式相乘\(h(x)=f(x)*g(x)=\sum\limits_{i=0}^{n+m-2}x^i\sum\limits_{j=0}^if_{i-j}s_j\)，得到
\(h(x)=4*x^4+13*x^3+28*x^2+27*x^1+18*x^0\)
把\(x=10\)带入其中，得到\(56088\)。也可以开始执行进位。
4 13 28 27 18
4 13 28 28 8
4 13 30 8 8
4 16 0 8 8
5 6 0 8 8
所以多项式乘法可以解决高精度问题
FFT解决KMP问题
多项式怎么解决KMP问题呢
设\(t_i\)表示翻转后的每个位置的值，\(s_i\)表示文本串的每个位置的值，作为系数（我把AZ改为了025，也可以用ascii码来代替，效果一样）。
例如ABCABC和ABC，修改为\(s(x)=0*x^0+1*x^1+2*x^2+0*x^3+1*x^4+2*x^5\)，\(t(x)=2*x^0+1*x^1+0*x^2\)
| \(i\) | \(t_i\) |
|---|---|
| 0 | 2 |
| 1 | 1 |
| 2 | 0 |
| \(i\) | \(s_i\) |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 0 |
| 4 | 1 |
| 5 | 2 |
计算\(h(x)=\sum\limits_{i=m-1}^{n-1} x^i\sum\limits_{j=0}^{m-1}(s_{i-j}-t_j)^2\)
#include <bits/stdc++.h>
using namespace std;
int h[1000],s[1000],t[1000];
string S,T;
int n,m;
int main(){cin>>S>>T;n=S.size();m=T.size();for(int i=0;i<n;i++)s[i]=S[i]-'a';reverse(T.begin(),T.end());for(int i=0;i<m;i++)t[i]=T[i]-'a';for(int i=m-1;i<=n;i++){for(int j=0;j<m;j++)h[i]=h[i]+(s[i-j]-t[j])*(s[i-j]-t[j]);printf("%d*x^%d\n",h[i],i);}
}
得到
| \(i\) | \(h_i\) |
|---|---|
| 2 | 0 |
| 3 | 6 |
| 4 | 6 |
| 5 | 0 |
这里\(h_i\)表示\(S[i-m+1,i]\)和\(T[0,m-1]\)每个位置的差值的平方的累加值。\(h_i\)恰好为\(0\)时，当且仅当\(S[i-m+1,i]==T[0,m-1]\)。
可以发现\(h(x)=\sum\limits_{i=m-1}^{n-1} x^i\sum\limits_{j=0}^{m-1}(s_{i-j}-t_j)^2\)可以改为\(h(x)=\sum\limits_{i=m-1}^{n-1} x^i\sum\limits_{j=0}^{m-1}(s_{i-j}-t_j)^4\)，可以改为\(h(x)=\sum\limits_{i=m-1}^{n-1} x^i\sum\limits_{j=0}^{m-1}(s_{i-j}-t_j)^6\)，但是不能改成\(h(x)=\sum\limits_{i=m-1}^{n-1} x^i\sum\limits_{j=0}^{m-1}(s_{i-j}-t_j)\)，因为\(h_i=0\)不能代表着\(S[i-m+1,i]==T[0,m-1]\)。
\(h(x)=\sum\limits_{i=m-1}^{n-1} x^i\sum\limits_{j=0}^{m-1}(s_{i-j}-t_j)^2\)这个式子可以修改为\(h(x)=\sum\limits_{i=m-1}^{n-1} x^i\sum\limits_{j=0}^{m-1}(s_{i-j}^2-2*s_{i-j}t_j+t_j^2)\)，\(s_{i-j}^2\)和\(t_j^2\)的累加和可以预处理前缀和得到，\(s_{i-j}t_j\)这里可以用FFT帮忙。
有问题啊，你FFT计算的是\(h(x)=f(x)*g(x)=\sum\limits_{i=0}^{n+m-2}x^i\sum\limits_{j=0}^if_{i-j}s_j\)，为什么你现在要计算\(\sum\limits_{i=m-1}^{n-1} 2 x^i\sum\limits_{j=0}^{m-1} s_{i-j}*t_j\)，很明显内部的\(\sum\)的上界不一样。
其实没问题，因为当\(j\in [m,i]\)时，\(t_j=0\)，因此\(\sum\limits_{j=0}^{m-1} s_{i-j}*t_j=\sum\limits_{j=0}^{i} s_{i-j}*t_j\)。
FFT计算距离为k的括号对
https://www.cnblogs.com/qywyt/p/17281504.html
有一个长度为\(n\)的括号序列，仅由(和)组成。如果括号序列的第\(i\)个位置是(，第j个位置是)，且\(j-i=k\)，那么我们称这是一对距离为\(k\)的括号对。
小Z想知道，对于所有的\(k\in [1,n-1]\)有多少个距离为\(k\)的括号对？
输入格式：
输入一行一个字符串\(s\)，保证只包含(和)且长度不超过\(2*10^5\)。
输出格式：
输出一行\(|s|-1\)个整数，从左到右依次表示距离为\(1\sim n-1\)的括号对数。数字之间用空格隔开
输入样例：
(()()(()))
输出样例：
3 3 3 3 1 2 2 2 1
对于为(的位置\(i\)，令f(x)里\(x^{-i}\)的系数为\(1\)，也就是\(f(x)=\sum\limits_{i=0}^{n-1}x^{-i}[s_i为左括号]\)。
为)的位置\(i\)，令g(x)里\(x^i\)的系数为\(1\)，也就是\(g(x)=\sum\limits_{i=0}^{n-1}x^i[s_i为右括号]\)。
例如(())视为\(f(x)=x^0+x^{-1}\)和\(g(x)=x^2+x^3\)
计算\(h(x)=f(x)*g(x)=x^1+2*x^2+x^3\)。
这样，h(x)的x^k的系数表明有几对()的距离恰好为k。
对于()()，令\(f(x)=x^0+x^{-2}\)，\(g(x)=x^1+x^3\)
\(h(x)=f(x)*g(x)=x^{-1}+2*x^1+x^3\)
这里的\(x^{-1}\)项系数为1，表明有一对()的距离为-1，也就是)在(的左边。
\(x^1\)系数为2表明有两对()距离为1，\(x^3\)的系数为1表明有一对(??)。
FFT计算允许位置偏差不超过k的"kmp"
CF528D
给出一个门限值 \(k\) 和两个只包含 \(\texttt{AGCT}\) 四种字符的基因串 \(S\) 和 \(T\)。现在你要找出在下列规则中 \(T\) 在 \(S\) 中出现了几次。
\(T\) 在 \(S\) 的第 \(i\) 个位置中出现，当且仅当把 \(T\) 的首字符和 \(S\) 的第 \(i\) 个字符对齐后，\(T\) 中的每一个字符能够在 \(S\) 中找到一个位置偏差不超过 \(k\) 的相同字符。
即对于所有的 \(j \in[1,|T|]\)，都存在一个 \(p \in [1,|S|]\) 使得 \(|(i+j-1)-p| \leq k\) 且 \(S_p=T_j\) 。
例如 \(k=1\) 时，\(\texttt{ACAT}\) 出现在 \(\texttt{AGCAATTCAT}\) 的 \(2\) 号， \(3\) 号和 \(6\) 号位置。 (编号从 \(1\) 开始。)
如果\(k=0\)可以\(kmp\)秒了
当\(k\)比较大时，考虑四个字母分别计算一下，每次计算时钦定正在考虑的字母是\(1\)，其他字母全为\(0\)。对\(S\)串的\(1\)做"扩散"\(k\)距离，再做\(FFT\)即可。（记得给T串做翻转）
例如\(S=1234123\)，\(T=1123\),\(k=1\)
先做\(1\)的，\(s(x)=x^0+x^1+x^3+x^4+x^5(1101110)\),\(t(x)=x^2+x^3(0011)\)，令做\(FFT\)求得\(h(x)=x^2+2*x^3+x^4+x^5+2*x^6+2*x^7+x^8(001211221)\)。
这里的\(1*x^4\)的\(1\)表示以\(S[1\sim 4](2341)\)和\(1123\)做匹配能有一个位置匹配上（\(S[1]=2\)这里被\(S[0]=1\)扩散成了\(1\)，然后\(S[1]\)和\(T[0]\)匹配上了）。
这里的\(2*x^6\)表示以\(S[3\sim 6](4123)\)和\(1123\)做匹配有两个位置匹配上了。未来可期，只要\(2\)有一个位置匹配上，\(3\)有一个位置匹配上就\(ans++\)。
这里的\(2*x^7\)表示以\(S[4\sim 7]\)和\(1123\)做匹配，有两个位置能匹配上。虽然现在有两个位置匹配上了，但是可以预见未来凑不够四个位置，不会令\(ans++\)。
再做\(2\)的，\(s(x)=x^0+x^1+x^2+x^4+x^5+x^6(2220222),t(x)=x^1(0100)，h(x)=x^1+x^2+x^3+x^5+x^6+x^7(01110111)\)。
再做\(3\)的，\(s(x)=x^1+x^2+x^3+x^5+x^6(0111011),t(x)=x^0(1000),h(x)=s(x)=x^1+x^2+x^3+x^5+x^6(0111011)\)
\(4\)的对应的\(t(x)\)为\(0\)，不用做。
把得到的\(h(x)\)加在一起，得到\((023413431)\)，这里面的两个\(4\)表明在这两个位置为结尾的子字符串\(s\)完全匹配上了\(t\)，\(ans++\)即可。
（课后题，为什么不能做四次kmp，四次都完全匹配上的位置ans++）
（课后题2，能不能用m次bitset）
我的FFT模板
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef double db;
typedef long long ll;
struct cp
{db x,y;cp(db real=0,db imag=0):x(real),y(imag){};cp operator +(cp b)const{return {x+b.x,y+b.y};}cp operator -(cp b)const{return {x-b.x,y-b.y};}cp operator*(cp b)const{return {x*b.x-y*b.y,x*b.y+y*b.x};}
};
using vcp=vector<cp>;
using Poly=vector<int>;
class Cipolla
{int P,I2{};using pll=pair<ll,ll>;
};
#define MUL(a,b) (ll(a)*(b)%P)
#define ADD(a,b) (((a)+=(b))>=P?(a)-=P:0)
#define SUB(a,b) (((a)-=(b))<0?9a)+=P:0)
const int P=1e9+7,N=2e5+10;
Poly getINV(int L){Poly inv(L);inv[1]=1;rep(i,2,L-1)inv[i]=MUL((P-P/i),inv[P%i]);return inv;}
int POW(ll a,int b=P-2,ll x=1)
{for(;b;b>>=1,a=a*a%P)if(b&1)x=x*a%P;return x;
}
//auto inv=getInv(N);
namespace FFT{const db pi=acos(-1);vcp Omega(int L){vcp w(L);w[1]=1;for(int i=2;i<L;i<<=1){auto w0=w.begin()+i/2,w1=w.begin()+i;cp wn(cos(pi/i),sin(pi/i));for(int j=0;j<i;j+=2)w1[j]=w0[j>>1],w1[j+1]=w1[j]*wn;}return w ;}auto W=Omega(1<<19);void DIF(cp *a,int n){cp x,y;for(int k=n>>1;k;k>>=1)for(int i=0;i<n;i+=k<<1)for(int j=0;j<k;j++)x=a[i+j],y=a[i+j+k],a[i+j+k]=(a[i+j]-y)*W[k+j],a[i+j]=x+y;}void IDIT(cp *a,int n){cp x,y;for(int k=1;k<n;k<<=1)for(int i=0;i<n;i+=k<<1)for(int j=0;j<k;j++)x=a[i+j],y=a[i+j+k]*W[k+j],a[i+j+k]=x-y,a[i+j]=x+y;const db Inv=1. /n;rep(i,0,n-1)a[i].x*=Inv,a[i].y*=Inv;reverse(a+1,a+n);}
}
namespace Polynomial{void DFT(vcp &a){FFT::DIF(a.data(),a.size());}void IDFT(vcp &a){FFT::IDIT(a.data(),a.size());}int norm(int n){return 1<<(__lg(n-1)+1);}void norm(Poly &a){if(!a.empty())a.resize(norm(a.size()),0);elsea={0};}vcp &dot(vcp &a,vcp &b){rep(i,0,a.size()-1)a[i]=a[i]*b[i];return a;}Poly operator *(ll k,Poly a){Poly ans;for(auto i:a)ans.push_back(k*i);return ans;}Poly operator *(Poly a,Poly b){int n=a.size()+b.size()-1;vcp c(norm(n));rep(i,0,a.size()-1)c[i].x=a[i];rep(i,0,b.size()-1)c[i].y=b[i];DFT(c),dot(c,c),IDFT(c),a.resize(n);rep(i,0,n-1)a[i]=(int)(c[i].y*.5+.5);return a;}
}
using namespace Polynomial;
char s[N];
int n;int main()
{Poly vec1(n),vec2(n);Poly ans=vec1*vec2;
}
