「UR#34」多项式乘法

2015年4月29日5,3422

贴俩模板

递归 750B 4000ms

#include<bits/stdc++.h>
#define pi acos(-1)
using namespace std;
typedef complex<double> E;
int n,m;
E a[262145],b[262145];
void fft(E *x,int n,int type)
{
    if(n==1)return;
	E l[n>>1],r[n>>1];
	for(int i=0;i<n;i+=2)
		l[i>>1]=x[i],r[i>>1]=x[i+1];
	fft(l,n>>1,type);fft(r,n>>1,type);
	E wn(cos(2*pi/n),sin(type*2*pi/n)),w(1,0),t;
	for(int i=0;i<n>>1;i++,w*=wn)
		t=w*r[i],x[i]=l[i]+t,x[i+(n>>1)]=l[i]-t;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0,x;i<=n;i++)scanf("%d",&x),a[i]=x;
	for(int i=0,x;i<=m;i++)scanf("%d",&x),b[i]=x;
	m=n+m;for(n=1;n<=m;n<<=1);
	fft(a,n,1);fft(b,n,1);
	for(int i=0;i<=n;i++)a[i]=a[i]*b[i];
	fft(a,n,-1);
	for(int i=0;i<=m;i++)
		printf("%d ",(int)(a[i].real()/n+0.5));
	return 0;
}

#include<bits/stdc++.h>

#define pi acos(-1)

using namespace std;

typedef complex<double> E;

int n,m;

E a[262145],b[262145];

void fft(E *x,int n,int type)

{

if(n==1)return;

E l[n>>1],r[n>>1];

for(int i=0;i<n;i+=2)

l[i>>1]=x[i],r[i>>1]=x[i+1];

fft(l,n>>1,type);fft(r,n>>1,type);

E wn(cos(2*pi/n),sin(type*2*pi/n)),w(1,0),t;

for(int i=0;i<n>>1;i++,w*=wn)

t=w*r[i],x[i]=l[i]+t,x[i+(n>>1)]=l[i]-t;

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=0,x;i<=n;i++)scanf("%d",&x),a[i]=x;

for(int i=0,x;i<=m;i++)scanf("%d",&x),b[i]=x;

m=n+m;for(n=1;n<=m;n<<=1);

fft(a,n,1);fft(b,n,1);

for(int i=0;i<=n;i++)a[i]=a[i]*b[i];

fft(a,n,-1);

for(int i=0;i<=m;i++)

printf("%d ",(int)(a[i].real()/n+0.5));

return 0;

}

非递归 830B 1200ms

#include<bits/stdc++.h>
#define N 262145
#define pi acos(-1)
using namespace std;
typedef complex<double> E;
int n,m,L;
int R[N];
E a[N],b[N];
void fft(E *a,int f)
{
	for(int i=0;i<n;i++)if(i<R[i])swap(a[i],a[R[i]]);
	for(int i=1;i<n;i<<=1)
	{
		E wn(cos(pi/i),f*sin(pi/i));
		for(int p=i<<1,j=0;j<n;j+=p)
		{
			E w(1,0);
			for(int k=0;k<i;k++,w*=wn)
			{
				E x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y;a[j+k+i]=x-y;
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0,x;i<=n;i++)scanf("%d",&x),a[i]=x;
	for(int i=0,x;i<=m;i++)scanf("%d",&x),b[i]=x;
	m=n+m;for(n=1;n<=m;n<<=1)L++;
	for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	fft(a,1);fft(b,1);
	for(int i=0;i<=n;i++)a[i]=a[i]*b[i];
	fft(a,-1);
	for(int i=0;i<=m;i++)
		printf("%d ",(int)(a[i].real()/n+0.5));
	return 0;
}