FFT模板
P3803 多项式乘法模板（FFT）
题意：
作者：是我菜了
给定n次和m次多项式的系数，要求计算这两个多项式乘积的系数
code：#include
using namespace std;
const double P=acos(-1.0);
struct CC{//复数
double x,y;
CC(double xx=0,double yy=0){x=xx,y=yy;}
CC operator+(const CC &a)const{return CC(x+a.x,y+a.y);}
CC operator-(const CC &a)const{return CC(x-a.x,y-a.y);}
CC operator*(const CC &a)const{return CC(x*a.x-y*a.y,x*a.y+y*a.x);}
};
void change(CC y[],int len){
for(int i=1,j=len/2;i<len-1;i++){
if(i=k){
j-=k;
k/=2;
}
if(j<k)j+=k;
}
}
void fft(CC y[],int len,int on){//on为1或者-1,-1的时候表示逆变换
change(y,len);
for(int h=2;h<=len;h<<=1){
CC wn(cos(-on*2*P/h),sin(-on*2*P/h));
for(int j=0;j<len;j+=h){
CC w(1,0);
for(int k=j;k<j+h/2;k++){
CC u=y[k];
CC t=w*y[k+h/2];
y[k]=u+t;
y[k+h/2]=u-t;
w=w*wn;
}
}
}
if(on==-1){
for(int i=0;i<len;i++){
y[i].x/=len;
}
}
}
//
const int maxm=4e6+5;
CC x1[maxm],x2[maxm];
int sum[maxm];
signed main(){
int n,m;scanf("%d%d",&n,&m);
int len=1;
while(len<n*2||len<m*2)len<<=1;
for(int i=0;i<=n;i++){
int x;scanf("%d",&x);
x1[i]=CC(x,0);
}
for(int i=n+1;i<len;i++)x1[i]=CC(0,0);
for(int i=0;i<=m;i++){
int x;scanf("%d",&x);
x2[i]=CC(x,0);
}
for(int i=m+1;i<len;i++)x2[i]=CC(0,0);
fft(x1,len,1);
fft(x2,len,1);
//memset(sum,0,sizeof sum);清空结果数组
for(int i=0;i<len;i++){
x1[i]=x1[i]*x2[i];
}
fft(x1,len,-1);
for(int i=0;i<=len;i++){
sum[i]=(int)(x1[i].x+0.5);
}
len=n+m;//相乘结果为n+m+1项,下标为0到n+m
for(int i=0;i<=len;i++){
printf("%d ",sum[i]);
}
return 0;
}
hdu1402 A * B Problem Plus
题意：
给定两个大整数a和b，计算a*b，a和b的长度不超过50000
解法：将每一位看作多项式的系数，然后相乘即可
注意最后要处理一下进位
#include
using namespace std;
const double P=acos(-1.0);
struct CC{//复数
double x,y;
CC(double xx=0,double yy=0){x=xx,y=yy;}
CC operator+(const CC &a)const{return CC(x+a.x,y+a.y);}
CC operator-(const CC &a)const{return CC(x-a.x,y-a.y);}
CC operator*(const CC &a)const{return CC(x*a.x-y*a.y,x*a.y+y*a.x);}
};
void change(CC y[],int len){
for(int i=1,j=len/2;i<len-1;i++){
if(i=k){
j-=k;
k/=2;
}
if(j<k)j+=k;
}
}
void fft(CC y[],int len,int on){//on为1或者-1,-1的时候表示逆变换
change(y,len);
for(int h=2;h<=len;h<<=1){
CC wn(cos(-on*2*P/h),sin(-on*2*P/h));
for(int j=0;j<len;j+=h){
CC w(1,0);
for(int k=j;k<j+h/2;k++){
CC u=y[k];
CC t=w*y[k+h/2];
y[k]=u+t;
y[k+h/2]=u-t;
w=w*wn;
}
}
}
if(on==-1){
for(int i=0;i<len;i++){
y[i].x/=len;
}
}
}
//
const int maxm=2e5+5;
char a[maxm],b[maxm];
CC x1[maxm],x2[maxm];
int sum[maxm];
signed main(){
while(scanf("%s%s",a,b)!=EOF){
int n=strlen(a);
int m=strlen(b);
int len=1;
while(len<n*2||len<m*2)len<<=1;
for(int i=0;i<n;i++)x1[i]=CC(a[n-i-1]-'0',0);//逆序存入
for(int i=n;i<len;i++)x1[i]=CC(0,0);
for(int i=0;i<m;i++)x2[i]=CC(b[m-i-1]-'0',0);//逆序存入
for(int i=m;i<len;i++)x2[i]=CC(0,0);
fft(x1,len,1);
fft(x2,len,1);
for(int i=0;i<len;i++){
x1[i]=x1[i]*x2[i];
}
fft(x1,len,-1);
memset(sum,0,sizeof sum);//清空结果数组
for(int i=0;i<len;i++){
sum[i]=(int)(x1[i].x+0.5);
}
for(int i=0;i=len)len++;
}
while(sum[len]==0&&len>0)len--;//去掉前导零
for(int i=len;i>=0;i--){
putchar(sum[i]+'0');
}
puts("");
}
return 0;
}
作者：是我菜了
