「BZOJ3527」[ZJOI2014] 力

2015年4月29日6,1323

qi乘进去，发现是裸的俩卷积。。。

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#define N 262144
#define pi acos(-1)
#define ll long long
using namespace std;
typedef complex<double> E;
int n,m,L;
int rev[N];
E f[N],_f[N],g[N],e1[N],e2[N];
void fft(E *a,int f)
{
	for(int i=0;i<n;i++)if(i>rev[i])swap(a[i],a[rev[i]]);
	for(int i=1;i<n;i<<=1)
	{
		E wn(cos(pi/i),f*sin(pi/i));
		for(int j=0;j<n;j+=(i<<1))
		{
			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;
			}
		}
	}
	if(f==-1)for(int i=0;i<n;i++)a[i]/=n;
}
int main()
{
	scanf("%d",&n);n--;
	for(int i=0;i<=n;i++)
	{
		double x;scanf("%lf",&x);
		f[i]=x;
		_f[n-i]=x;
	}
	for(int i=1;i<=n;i++)g[i]=(1.0/i/i);
	m=2*n;for(n=1;n<=m;n<<=1)L++;
	for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
	fft(f,1);fft(g,1);fft(_f,1);
	for(int i=0;i<n;i++)e1[i]=f[i]*g[i];
	for(int i=0;i<n;i++)e2[i]=_f[i]*g[i];
	fft(e1,-1);fft(e2,-1);
	for(int i=0;i<=m/2;i++)
		printf("%.3lf\n",e1[i].real()-e2[m/2-i].real());
	return 0;
}

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<complex>

#include<iostream>

#include<algorithm>

#define N 262144

#define pi acos(-1)

#define ll long long

using namespace std;

typedef complex<double> E;

int n,m,L;

int rev[N];

E f[N],_f[N],g[N],e1[N],e2[N];

void fft(E *a,int f)

{

for(int i=0;i<n;i++)if(i>rev[i])swap(a[i],a[rev[i]]);

for(int i=1;i<n;i<<=1)

{

E wn(cos(pi/i),f*sin(pi/i));

for(int j=0;j<n;j+=(i<<1))

{

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;

}

if(f==-1)for(int i=0;i<n;i++)a[i]/=n;

}

int main()

{

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

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

{

double x;scanf("%lf",&x);

f[i]=x;

_f[n-i]=x;

}

for(int i=1;i<=n;i++)g[i]=(1.0/i/i);

m=2*n;for(n=1;n<=m;n<<=1)L++;

for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));

fft(f,1);fft(g,1);fft(_f,1);

for(int i=0;i<n;i++)e1[i]=f[i]*g[i];

for(int i=0;i<n;i++)e2[i]=_f[i]*g[i];

fft(e1,-1);fft(e2,-1);

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

printf("%.3lf\n",e1[i].real()-e2[m/2-i].real());

return 0;

}

« 「BZOJ2194」快速傅立叶之二「BZOJ3160」万径人踪灭 »

YMX

黄学长，你的每道题都有题面，我感到很棒，然而，当我来这道题找题面时，却发现没有……

hzwer

http://wenku.baidu.com/link?url=BRF67OnoXtD8G4s0FmeR_8rxkR88Nn5YE-zMdICzpGCg18hRvPIZHm_PZfsGQUhNNpmRWCmfHKwScqgLYCYyuZiwAUk8ZapNehaGI7dDyKK

亍·彳

膜膜膜膜膜膜膜膜

hzwer.com _ Home | http://hzwer.com

「BZOJ3527」[ZJOI2014] 力

分类目录

热门文章

Myfriends

近期评论