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}$
这能一眼秒是卷积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\n",a[i].real()/m);
return 0;
}
原文：http://www.cnblogs.com/MashiroSky/p/6337063.html