笔记-[ZJOI2014]力

[ZJOI2014]力

\[\begin{split}
E_j=&\sum_{i=1}^{j-1}\frac{q_i}{(i-j)^2}-\sum_{i=j+1}^{n}\frac{q_i}{(i-j)^2}\\
=&\sum_{i=1}^{j}\frac{q_i}{(i-j)^2}-\sum_{i=j}^{n}\frac{q_i}{(i-j)^2}\\
\end{split}\\
\begin{cases}
f_i=q_i\\
g_i=\frac 1{i^2}\\
\end{cases}
\Rightarrow
ansa_i=\sum_{j+k=i}f_j\cdot g_k\\
\begin{cases}
f_i=q_{n-i+1}\\
g_i=\frac 1{i^2}\\
\end{cases}
\Rightarrow
ansb_i=\sum_{j+k=i}f_j\cdot g_k\\
ans_i=ansa_i-ansb_{n+1-i}\\
\]

#include <bits/stdc++.h>

using namespace std;

//Start

#define lng long long

#define db double

#define mk make_pair

#define pb push_back

#define fi first

#define se second

#define rz resize

const int inf=0x3f3f3f3f;

const lng INF=0x3f3f3f3f3f3f3f3f;

//Data

const int N=4e5;

int n;

//FFT

const db Pi=acos(-1);

typedef pair<db,db> cp;

cp operator+(const cp a,const cp b){return mk(a.fi+b.fi,a.se+b.se);}

cp operator-(const cp a,const cp b){return mk(a.fi-b.fi,a.se-b.se);}

cp operator*(const cp a,const cp b){return mk(a.fi*b.fi-a.se*b.se,a.fi*b.se+a.se*b.fi);}

vector<cp> a(N+7),b(N+7),c(N+7);

int lim=1,ln,r[N+7];

void FFT(vector<cp>&f,int t){

	for(int i=0;i<lim;i++)if(i<r[i]) swap(f[i],f[r[i]]);

	for(int mid=1;mid<lim;mid<<=1){

		cp wn(mk(cos(Pi/mid),sin(Pi/mid)*t));

		for(int j=0;j<lim;j+=mid<<1){

			cp w(mk(1,0));

			for(int k=j;k<mid+j;w=w*wn,k++){

				cp x(f[k]),y(w*f[mid+k]);

				f[k]=x+y,f[mid+k]=x-y;

			}

		}

	}

}

//Main

int main(){

	scanf("%d",&n);

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

		scanf("%lf",&a[i].fi);

		b[n+1-i].fi=a[i].fi;

		c[i].fi=1.0/db(i)/db(i);

	}

	while(lim<=(n<<1)) lim<<=1,ln++;

	for(int i=0;i<lim;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(ln-1));

	FFT(a,1),FFT(b,1),FFT(c,1);

	for(int i=0;i<lim;i++) a[i]=a[i]*c[i],b[i]=b[i]*c[i];

	FFT(a,-1),FFT(b,-1);

	for(int i=0;i<lim;i++) a[i].fi/=lim,b[i].fi/=lim;

	for(int i=1;i<=n;i++) printf("%.7lf\n",a[i].fi-b[n+1-i].fi);

	return 0;

}

巴特西

笔记-[ZJOI2014]力

最新文章

热门文章