2017.8.26 力 思考记录

原题的式子把分母乘进去，然后式子中i-j随枚举变化也是定值，所以直接设b【i】=1/i^2

然后第一个式子就是：  ，可看为多项式乘法中的一项的系数   

第二个式子差是定值，再设一个aa【i】=a【n-i】 然后第二个式子也变成了:

两个fft相减即可

注意complex定义没有等号，swap把小的放前面

码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<complex>
using namespace std;
#define pi acos(-1)
#define N 300005
typedef complex<double>E;
int l,n,r[N<<1],m;
E a[N],b[N],c[N],aa[N],d[N];
void fft(E *a,int f)
{
	int i,j,k;
	for(i=0;i<n;i++)if(i>r[i])swap(a[i],a[r[i]]);
	for(i=0;i<n;i++)
	cout<<a[i]<<endl;	
	for(i=1;i<n;i<<=1)
	{

	E wn(cos(pi/i),f*sin(pi/i));
    for(j=0;j<n;j+=(i<<1))
	{
		E w(1,0);
	for(k=0;k<i;k++,w*=wn)
	{
	E x=a[j+k],y=w*a[j+i+k];
	a[j+k]=x+y;a[j+k+i]=x-y;		
	}		
    }
	}
	if(f==-1)for(i=0;i<n;i++)a[i]/=n;
}
int main()
{
	int i,j,k;
	scanf("%d",&n);n--;
	for(i=0;i<=n;i++)
	{
		scanf("%lf",&a[i]);
		aa[n-i]=a[i];
	}
for(i=1;i<=n;i++)b[i]=(1.0/i/i);	
	m=2*n;
	for(n=1;n<=m;n<<=1)++l;
for(i=0;i<n;i++)
	r[i]=((r[i>>1]>>1)|((1&i)<<(l-1)));
	fft(a,1);
	fft(b,1);
	for(i=0;i<n;i++)c[i]=a[i]*b[i];
	fft(c,-1);
	fft(aa,1);
	for(i=0;i<n;i++)d[i]=aa[i]*b[i];	
	fft(d,-1);
	for(i=0;i<=m/2;i++)
	{
	printf("%.6lf\n",c[i].real()-d[m/2-i].real());
    }
}