首页 > 其他 > 详细

BZOJ 3527 【ZJOI2014】 力

时间:2017-02-06 21:57:50      阅读:220      评论:0      收藏:0      [点我收藏+]

题目链接:

  听说这道题是\(FFT\)板子题,于是我就来写了……

  首先可以发现这个式子:\[E_i=\sum_{j<i}\frac{q_j}{(i-j)^2}-\sum_{j>i}\frac{q_j}{(i-j)^2} \]

  然后可以对两半分别考虑一下。发现下标刚好是\(j+(i-j)=i\),于是我们就可以开始构(gao)造(shi)了,弄俩多项式出来:

\[A_1(x)=0x^0+q_1x^1+q_2x^2+……+q_nx^n\]

\[A_2(x)=\frac{-1}{n^2}x^0+\frac{-1}{(n-1)^2}x^1+……+0x^n+……+\frac{1}{(n-1)^2}x^{2n-1}+\frac{1}{n^2}x^{2n}\]

  把这两个多项式乘起来,取下标为\((n,2n]\)的系数即为答案。

  实际上,把多函数\(A_1(x)\)的系数全部左移一位也是可以的,只不过答案的区间要变一下。

  下面贴代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<complex>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define C complex<double>
#define maxn 300010
#define pi (acos(-1))
 
using namespace std;
typedef double llg;
 
int n,m,L,R[maxn];
C a[maxn],b[maxn];

llg gi(int x){return 1.0*x*x;}
void fft(C *a){
	for(int i=0;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);
	for(int i=1;i<n;i<<=1){
		C wn(cos(pi/i),sin(pi/i)),x,y;
		for(int j=0;j<n;j+=(i<<1)){
			C w(1,0);
			for(int k=0;k<i;k++,w*=wn){
				x=a[j+k]; y=w*a[j+i+k];
				a[j+k]=x+y; a[j+i+k]=x-y;
			}
		}
	}
}
 
int main(){
	File("a");
	scanf("%d",&n); m=n;
	for(int i=0;i<n;i++) scanf("%lf",&a[i].real());
	for(int i=0;i<n;i++) b[i].real()=-1.0/gi(n-i),b[2*n-i]=-b[i];
	for(n=1;n<=(m<<1);n<<=1) L++;
	for(int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	fft(a); fft(b);
	for(int i=0;i<n;i++) a[i]*=b[i];
	fft(a); reverse(a+1,a+n);
	for(int i=m+1;i<=(m<<1);i++) printf("%.6lf\n",a[i].real()/n);
	return 0;
}

BZOJ 3527 【ZJOI2014】 力

原文:http://www.cnblogs.com/lcf-2000/p/6371720.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!