【bzoj3527】 Zjoi2014—力

http://www.lydsy.com/JudgeOnline/problem.php?id=3527 (题目链接)

题意

　　$${F_i=sum_{j<i} {frac{q_iq_j}{(i-j)^2}}   -   sum_{j>i} {frac{q_iq_j}{(i-j)^2}}}$$

　　给出${q_i}$求${E_i=F_i/q_i}$

Solution

　　这能一眼秒是卷积w(ﾟДﾟ)w，我怎么完全看不出来，这太强了吧。。

　　两边同时约掉一个${q_i}$，式子就变的和谐了很多：$${E_i=sum_{j<i} {frac{q_j}{(i-j)^2}}   -   sum_{j>i} {frac{q_j}{(i-j)^2}}}$$

　　然后到这里我就不知道了。。听说要构造两个多项式，然后${E_i}$就可以表示为他们乘积的某一项的系数。。$${A(x)=sum_{i=0}^{n-1} q_{i+1}*x^i}$$$${B(x)=sum_{i=0}^{n-2}{-frac{x^i}{(n-i-1)^2}} + 0*x^{n-1} + sum_{i=n}^{2n-2} {frac{x^i}{(n-i+1)^2}}}$$

　　最后只要输出第${n}$项到第${2n-1}$项的系数就是答案。

　　一脸懵逼→_→

细节

　　注意数组大小，注意下标与次数

代码

// bzoj3527
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;

typedef complex<double> E;
const int maxn=200010;
E a[maxn<<2],b[maxn<<2];
int n,m;

namespace FFT {
	int rev[maxn<<3],L;
	void FFT(E *a,int f) {
		for (int i=0;i<m;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
		for (int i=1;i<m;i<<=1) {
			E wn(cos(Pi/i),f*sin(Pi/i));
			for (int p=i<<1,j=0;j<m;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;
				}
			}
		}
	}
	void Init() {
		int k=n*3-3;
		for (m=1;m<=k;m<<=1) L++;
		for (int i=0;i<m;i++) rev[i]=(rev[i>>1]>>1) | ((i&1)<<(L-1));
		FFT(a,1);FFT(b,1);
		for (int i=0;i<m;i++) a[i]*=b[i];
		FFT(a,-1);
	}
}

int main() {
	scanf("%d",&n);
	double x;
	for (int i=1;i<=n;i++) scanf("%lf",&x),a[i-1]=x;
	for (int i=0;i<=n-2;i++) b[i]=-1.0/(n-1-i)/(n-1-i);
	for (int i=n;i<=2*n-2;i++) b[i]=1.0/(n-1-i)/(n-1-i);
	FFT::Init();
	for (int i=n-1;i<2*n-1;i++) printf("%.3lf
",a[i].real()/m);
	return 0;
}