首页 > 代码库 > bzoj3527 [Zjoi2014]力
bzoj3527 [Zjoi2014]力
Description
给出n个数qi,给出Fj的定义如下:
令Ei=Fi/qi,求Ei.
Input
第一行一个整数n。
接下来n行每行输入一个数,第i行表示qi。
n≤100000,0<qi<1000000000
Output
n行,第i行输出Ei。与标准答案误差不超过1e-2即可。
Sample Input
5
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880
4006373.885184
15375036.435759
1717456.469144
8514941.004912
1410681.345880
Sample Output
-16838672.693
3439.793
7509018.566
4595686.886
10903040.872
3439.793
7509018.566
4595686.886
10903040.872
正解:FFT。
不难发现,这个式子可以分解成两个多项式,即0+q[1]x0+q[2]x0^2+q[3]xo^3+...+q[n]x0^n,和0+1/(1*1)x0+1/(2*2)x0^2+1/(3*3)x0^3+...+1/(n*n)x0^n。然后FFT以后就取1..n项,如果是减法那一个就是把第一个多项式倒过来,并且把最后的答案也倒过来,前面那个答案与它相减就好。
//It is made by wfj_2048~ #include <algorithm> #include <iostream> #include <complex> #include <cstring> #include <cstdlib> #include <cstdio> #include <vector> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define inf (1<<30) #define pi acos(-1) #define NN (500010) #define il inline #define RG register #define ll long long #define C complex<double> using namespace std; int rev[NN],n,N,M,lg; double q[NN],ans[NN]; C a[NN],b[NN],c[NN]; il void FFT(C *a,RG int n,RG int f){ for (RG int i=0;i<n;++i) if (i<rev[i]) swap(a[i],a[rev[i]]); for (RG int i=1;i<n;i<<=1){ C wn(cos(pi/i),sin(f*pi/i)),x,y; for (RG int j=0;j<n;j+=(i<<1)){ C w(1,0); for (RG int k=0;k<i;++k,w*=wn){ x=a[j+k],y=w*a[j+k+i]; a[j+k]=x+y,a[j+k+i]=x-y; } } } return; } il void work(){ scanf("%d",&n); for (RG int i=1;i<=n;++i) scanf("%lf",&q[i]); for (RG int i=1;i<=n;++i) a[i]=q[i]; for (RG int i=1;i<=n;++i) b[i]=1.0/i/i; M=2*(n+1); for (N=1;N<=M;N<<=1) lg++; for (RG int i=0;i<=N;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1)); FFT(a,N,1),FFT(b,N,1); for (RG int i=0;i<N;++i) a[i]*=b[i]; FFT(a,N,-1); for (RG int i=1;i<=n;++i) c[i]=q[n-i+1]; FFT(c,N,1); for (RG int i=0;i<N;++i) c[i]*=b[i]; FFT(c,N,-1); for (RG int i=1;i<=n;++i) ans[i]=a[i].real()/N-c[n-i+1].real()/N; for (RG int i=1;i<=n;++i) printf("%0.3lf\n",ans[i]); return; } int main(){ work(); return 0; }
bzoj3527 [Zjoi2014]力
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。