$\Huge{违规紫杉}$

$\Huge{本题为站外求助}$

多项式乘法

两个一元n次多项式f(x),g(x)，x^i项系数分别为A_i,B_i（i=0,1,...n），求f(x)*g(x)的各项系数

输入输出格式

输入格式

第一行一个正整数n（<=50000）

第二行n+1个整数A_n,A_n-1...A_0，表示f(x)的各项系数

第三行n+1个整数B_n,B_n-1...B_0，表示g(x)的各项系数

所有系数的绝对值不超过1000，并且A_n、B_n不为0 输出格式

一行2n+1个整数，表示f(x)*g(x)的各项系数（高次项在前）

输入输出样例

输入样例#1:

2

1 2 3

4 5 6

输出样例#1:

4 13 28 27 18

输入样例#2: 无 输出样例#2: 无 输入样例#3: 无 输出样例#3: 无

说明

样例说明： (x^2+2x+3)*(4x^2+5x+6)=4x^4+13x^3+28x^2+27x+

代码：

#include<cmath>
#include<cstdio>
#include<bits/stdc++.h>
const double pi=acos(-1.0);
int N,M,rev[0x200005];
struct Complex{
	double a,b;
	Complex(){}
	Complex(const double &ia,const double &ib){a=ia,b=ib;}
	inline Complex operator+(const Complex &x){return Complex(a+x.a,b+x.b);}
	inline Complex operator-(const Complex &x){return Complex(a-x.a,b-x.b);}
	inline Complex operator*(const Complex &x){return Complex(a*x.a-b*x.b,a*x.b+b*x.a);}
}fa[0x200005],ga[0x200005];
void swap(Complex &x,Complex &y){Complex t=x;x=y;y=t;}
int getint(){
	char c;
	for(;c=getchar(),c<'0' || c>'9';);
	return c&0xf;
}
void putint(const int num){
	if(num>=10)
		putint(num/10);
	putchar(num%10|'0');
}
void fft(Complex *a,const bool &inv){
	for(register int i=0;i<=N;++i)	if(i<rev[i])	swap(a[i],a[rev[i]]);
	for(register int n=2,l,k;n<=N;n<<=1){
		const register int bn=n>>1;
		register Complex w1(cos(2.0*pi/n),sin(2.0*pi/n));
		if(inv)	w1.b=-w1.b;
		for(l=0;l<=N;l+=n){
			register Complex wk(1.0,0.0),t,*la=a+l,*ra=a+l+bn;
			for(k=0;k<bn;++k){
				t=wk*ra[k];
				ra[k]=la[k]-t;
				la[k]=la[k]+t;
				wk=wk*w1;
			}
		}
	}
}
inline void init(){
	register int i;
	scanf("%d",&M);N=M;
	for(i=N;i>=0;--i)	fa[i].a=getint();
	for(i=M;i>=0;--i)	ga[i].a=getint();
	for(M+=N,N=1;N<=M;N<<=1);
	for(i=0;i<=N;++i)	rev[i]=(rev[i>>1]>>1)|((i&1)?(N>>1):0);
}
inline void solve(){
	fft(fa,false),fft(ga,false);
	for(register int i=0;i<N;++i)	fa[i]=fa[i]*ga[i];
	fft(fa,true);
	for(register int i=M;i>=0;--i)	putint((int)(fa[i].a/N+0.49)),putchar(' ');
}
int main(){
	init();
	solve();
	return 0;
}