洛谷 P1919 【模板】A*B Problem升级版(FFT快速傅里叶)

题目来源

吐槽下P3803都是紫题...

真心好写,本想一遍过的...但是

洛谷 P1919 【模板】A*B Problem升级版(FFT快速傅里叶)

我真是太菜了...

 #include<bits/stdc++.h>
using namespace std;
const int MAXN=;
const double pi=acos(-1.0);
char x[MAXN],y[MAXN];
int sum,lena,lenb,l;
int TT[MAXN],c[MAXN];
int r;
int n,m;
struct Node{
//int x;
double x;
double y;
Node (double x1=,double y1=){
x=x1,y=y1;
}
}a[MAXN],b[MAXN];
Node operator * (Node x,Node y){
return Node(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);
}
Node operator + (Node x,Node y){
return Node(x.x+y.x,x.y+y.y);
}
Node operator - (Node x,Node y){
return Node(x.x-y.x,x.y-y.y);
}
inline void fft(Node *g,double tf){
for (int i=;i<sum;++i)
if (i<c[i])
swap(g[i],g[c[i]]);
for (int j=;j<sum;j<<=){
Node T(cos(pi/j),tf*sin(pi/j));
for (int k=;k<sum;k+=(j<<)){
Node T1(,);
for (int l=;l<j;l++,T1=T*T1){
Node x1=g[k+l];
Node y1=T1*g[k+j+l];
g[k+l]=x1+y1;
g[k+j+l]=x1-y1;
}
}
}
}
int main(){
scanf("%d",&n);
scanf("%s%s",x,y);
//printf("%s",x);
for (int i=n-;i>=;i--){
a[lena++].x=x[i]-;
b[lenb++].x=y[i]-;
}
sum=;
while (sum<n+n) sum<<=,l++;
for (int i=;i<=sum;++i)
c[i]=(c[i>>]>>)|((i&)<<(l-));
fft(a,),fft(b,);
for (int i=;i<=sum;++i)
a[i]=a[i]*b[i];
fft(a,-);
for (int i=;i<=sum;++i){
TT[i]+=(int) (a[i].x/sum+0.5);
if (TT[i]>=){
TT[i+]+=TT[i]/;
TT[i]%=;
if (i==sum)
sum++;
}
}
while (!TT[sum] && sum>=)
sum--;
sum++;
while (--sum>=)
printf("%d",TT[sum]);
return ;
}
上一篇:POJ2159 ancient cipher - 思维题


下一篇:【高德地图API】如何获得行政区域?如何制作行政规划图?