bzoj3527 [Zjoi2014]力

NO IMAGE

Description


給出n個數qi,給出Fj的定義如下:

Fj=∑i&lt;jqiqj(i−j)2−∑j&lt;iqiqj(i−j)2″ role=”presentation”>Fj=∑i<jqiqj(i−j)2−∑j<iqiqj(i−j)2Fj=∑i<jqiqj(i−j)2−∑j<iqiqj(i−j)2

F_j=\sum_{i<j}{\frac{q_iq_j}{(i-j)^2}}-\sum_{j<i}{\frac{q_iq_j}{(i-j)^2}}
令Ei=Fi/qi,求Ei.

n≤100000,0

Solution


巨坑,注意看清ij區別
帶一下qi發現Ei=∑j&lt;iqj(i−j)2−∑i&lt;jqj(i−j)2″ role=”presentation”>Ei=∑j<iqj(i−j)2−∑i<jqj(i−j)2Ei=∑j<iqj(i−j)2−∑i<jqj(i−j)2E_i=\sum_{j<i}{\frac{q_j}{(i-j)^2}}-\sum_{i<j}{\frac{q_j}{(i-j)^2}}
令ai=qi” role=”presentation”>ai=qiai=qia_i=q_i,bi=1i2″ role=”presentation”>bi=1i2bi=1i2b_i=\frac{1}{i^2},前半部分就是ab的卷積,後半部分同理只是把b倒過來。打死我也不寫蝴蝶變換,能過就行

Code


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <complex>
#define rep(i,st,ed) for (register int i=st;i<=ed;  i)
typedef std:: complex <double> com;
const int N=262145;
const double pi=3.1415926535897932;
com a[N],b[N],c[N],d[N];
void FFT(com *c,int len,int f) {
if (len==1) return ;
com wn(cos(2.0*pi/len),sin(2.0*f*pi/len)),w(1,0),t;
com c1[len/2],c2[len/2];
rep(i,0,len/2-1) {
c1[i]=c[i*2];
c2[i]=c[i*2 1];
}
FFT(c1,len/2,f); FFT(c2,len/2,f);
for (register int i=0;i<len/2;i  ,w*=wn) {
t=c2[i]*w;
c[i]=c1[i] t;
c[i len/2]=c1[i]-t;
}
}
void calc(com *a,com *b,int len) {
len*=2;
int n=1; while (n<=len) n*=2;
FFT(a,n,1); FFT(b,n,1);
rep(i,0,n) a[i]*=b[i];
FFT(a,n,-1);
rep(i,0,len) a[i]=a[i]/(double)n;
}
int main(void) {
int n; scanf("%d",&n);
rep(i,1,n) {
scanf("%lf",&a[i-1]); b[n-i]=a[i-1];
c[i]=d[i]=1.0/i/i;
}
calc(a,c,n-1); calc(b,d,n-1);
rep(i,0,n-1) {
printf("%.3lf\n", a[i].real()-b[n-1-i].real());
}
return 0;
}