FFT求调
查看原帖
FFT求调
525234
__int128__楼主2023/4/30 18:41

RT,WA on 5,RE on 8,9,不知道问题在哪里/kk

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<bitset>
#include<map>
#include<set>
#include<unordered_map>
#include<ctime>
#include<random>
#define gc getchar
#define pc putchar
#define p__ puts("")
#define debug puts("-1")
#define double long double
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define reprange(a,b,c,d) for(int a=b;a<=c;a+=d)
#define perrange(a,b,c,d) for(int a=b;a>=c;a-=d)
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define per(a,b,c) for(int a=b;a>=c;a--)
#define reprange(a,b,c,d) for(int a=b;a<=c;a+=d)
#define perrange(a,b,c,d) for(int a=b;a>=c;a-=d)
#define int long long
#define double long double
using namespace std;
inline int rd(){
	int x=0,f=1;char ch=gc();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
	while(isdigit(ch)){x=x*10+ch-48;ch=gc();}return x*f;
}
inline void write(int x,char ch='\0'){
	if(x<0){x=-x;pc('-');}
	int y=0;char z[30];
	while(!y||x)z[y++]=x%10+48,x/=10;
	while(y--)pc(z[y]);if(ch!='\0')pc(ch);
}
const int maxn=1e7+5;
const double pi=acos(-1.0);
int n,m; 
struct complex{
	double real,imag;
}a[maxn],b[maxn];
complex operator+(complex p,complex q){
	return (complex){p.real+q.real,p.imag+q.imag};
} 
complex operator-(complex p,complex q){
	return (complex){p.real-q.real,p.imag-q.imag};
}
complex operator*(complex p,complex q){
	return (complex){p.real*q.real-p.imag*q.imag,p.real*q.imag+p.imag*q.real};
}
int lim,wei,omega[maxn];
void fft(complex *arr,int typ){
	rep(i,0,lim-1)if(i<omega[i])swap(arr[i],arr[omega[i]]);
	for(int u=1;u<lim;u<<=1){
		complex wn=(complex){cos(pi/u),typ*sin(pi/u)};
		int len=u<<1;
		reprange(i,0,lim-1,len){
			complex w=(complex){1,0};
			rep(j,0,u-1){
				complex p=arr[i+j],q=w*arr[i+j+u];
				arr[i+j]=p+q,arr[i+j+u]=p-q;
				w=w*wn;
			}
		}
	}
	if(typ==-1){
		rep(i,0,lim)a[i].real/=lim;
	}
}
signed main(){
	n=rd(),m=rd();rep(i,0,n)scanf("%Lf",&a[i].real);rep(i,0,m)scanf("%Lf",&b[i].real);
	lim=1;while(lim<=n+m)lim<<=1,wei++;
	rep(i,0,lim-1)omega[i]=(omega[i>>1]>>1)|((i&1)<<(wei-1));
	fft(a,1);fft(b,1);rep(i,0,lim)a[i]=a[i]*b[i];fft(a,-1);
	rep(i,0,n+m)printf("%.0Lf ",a[i].real);
}
2023/4/30 18:41
加载中...