刚学 FFT,样例不过求救
查看原帖
刚学 FFT,样例不过求救
368204
ShanQing楼主2024/11/3 16:16

样例输出 5 2 1 4,盯真能力不足对比同学 AC 代码盯不出任何问题。

#include <bits/stdc++.h>
//#include <windows.h>
#define ED cerr<<endl;
#define TS cerr<<"I AK IOI"<<endl;
#define cr(x) cerr<<x<<endl;
#define cr2(x,y) cerr<<x<<" "<<y<<endl;
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<endl;
#define cr4(x,y,z,w) cerr<<x<<" "<<y<<" "<<z<<" "<<w<<endl;
#define pii pair<int,int>
#define epb emplace_back
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define ll long long
//#define ull unsigned long long
using namespace std;
const int N=1e6+5,INF=2e9,mod=1e9+7;
const double pi=acos(-1);
int n,m,lim=1,l=0;
int r[N<<2];

inline void read(int &x) {
	int f=1;char s=getchar();x=0;
	while(s<'0'||s>'9') {
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9') {
		x=(x<<3)+(x<<1)+(s^48);
		s=getchar();
	}
	x*=f;
}

struct Complex {
	double x,y;
	Complex(double _x=0,double _y=0) {
		x=_x,y=_y;
	}
	
	Complex operator+(const Complex &W) const {
		return Complex(x+W.x,y+W.y);
	}
	
	Complex operator-(const Complex &W) const {
		return Complex(x-W.x,y-W.y);
	}
	
	Complex operator*(const Complex &W) const {
		return Complex(x*W.x-y*W.y,x*W.y+y*W.x);
	}
}f[N],g[N];

void FFT(Complex a[],int op) {
	for(int i=0;i<lim;++i) {
		if(i<r[i]) swap(a[i],a[r[i]]);
	}
	for(int mid=1;mid<lim;mid<<=1) {
		Complex Wn=(cos(pi/mid),op*sin(pi/mid));
		for(int j=0;j<lim;j+=(mid<<1)) {
			Complex w(1,0);
			for(int k=0;k<mid;++k,w=w*Wn) {
				Complex x=a[j+k],y=w*a[j+k+mid];
				a[j+k]=x+y,a[j+k+mid]=x-y;
			}
		}
	}
}

int main()
{
	read(n),read(m);int re;
	for(int i=0;i<=n;++i) read(re),f[i].x=re;
	for(int i=0;i<=m;++i) read(re),g[i].x=re;
	while(lim<=n+m) lim<<=1,++l;
	for(int i=0;i<lim;++i) {
		r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	}
	FFT(f,1),FFT(g,1);
	for(int i=0;i<=lim;++i) f[i]=f[i]*g[i];
	FFT(f,-1);
	for(int i=0;i<=n+m;++i) {
		printf("%d ",(int)(f[i].x/lim+0.5));
	}
	return 0;
}

2024/11/3 16:16
加载中...