FFT模版求条

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define PII pair<int,int>
#define pi(x,y) (make_pair(x,y))
#define fi(x) (x.first)
#define se(x) (x.second)
#define bit(x) (__builtin_popcount(x))
#define I cin>>
#define O cout<<
const ld eps=1e-8;
const ll inf=2e18;
const ld ldinf=1e9;
const ll MOD1=998244353;
const ll MOD2=1e9+7;
const ld Pi=acosl(-1.0l);
class poly{//多项式
private:
	vector<complex<ld> > arr;
	ll size;
	public:	
	void resize(int SIZE) {
		if(SIZE){
			ll n=1;
			while(n<SIZE) n<<=1;
			size=n;
		}else size=0;
		arr.resize(size);
	}
	poly(ll SIZE=0) {
		resize(SIZE);
	}
	complex<ld>& operator[](int idx){
		return arr[idx];
	}
	void FFT_change(){
		vector<int> rev(size);
		rev[0]=0;
		for(int i=1;i<size;i++){
			rev[i]=rev[i>>1]>>1;
			if(i&1) rev[i]|=size>>1;
		}
		for(int i=0;i<size;i++){
			if(i<rev[i]) swap(arr[i],arr[rev[i]]);
		}
	}
	void FFT(int rev){
		FFT_change();
		for(int i=2;i<=size;i<<=1){
			complex<ld> cp(cosl(2.0*Pi/i),-sinl(2.0*rev*Pi/i));
			for(int j=0;j<size;j+=i){
				complex<ld> w(1,0);
				for(int k=j;k<j+i/2;k++){
					complex<ld> s1=arr[k],s2=w*arr[k+i/2];
					arr[k]=s1+s2,arr[k+i/2]=s1-s2;
					w*=cp;
				}
			}
		}
		if(rev==-1){
			for(int i=0;i<size;i++) arr[i]/=size;
		}
	}
	friend poly operator*(poly p1, poly p2){
		int n=1;
		while(n<p1.size+p2.size-1) n<<=1;
		p1.resize(n);
		p2.resize(n);
		p1.FFT(1),p2.FFT(1);
		poly ans(n);
		for(int i=0;i<ans.size;i++) ans[i]=p1[i]*p2[i];
		ans.FFT(-1);
		return ans;
	}
	friend void operator*=(poly &d1, poly d2){
		d1=d1*d2;
	}
};
poly p1,p2;
int n,m;
signed main() {
	//	freopen(".in", "r", stdin);
	//  freopen("out.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	I n >> m;
	p1.resize(n+1);
	p2.resize(m+1);
	for(int i=0;i<=n;i++) I p1[i];
	for(int i=0;i<=m;i++) I p2[i];
	p1*=p2;
	for(int i=0;i<n+m+1;i++) O round(p1[i].real()) << " ";
	return 0;
}