样例输出 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;
}