测评链接
题目大意：
给定$n$个数$q_1,q_2,…q_n$，定义：
对$1\leq i \leq n$，求$E_i$的值。
数据范围
对于$100\%$的数据，$1 \leq n \leq 10^5,0<q_i<10^9$。
解题过程：
根据题意：
观察到这个式子有大量重复元素，那么不妨设出来方便表示：
即：
考虑将式子化为卷积的形式（之后解释）：
卷积：形如$\sum^{n-1}_1{F_i*G_{n-i}}$的式子
显然原式已有一部分为卷积形式，那么考虑另一部分。
考虑将序列倒转，倒转后的序列满足$C_i=A_{n-i+1}$，则原式：
可化为卷积：
最终得到的就是：
算法优化：
现在这个算法的时间复杂度仍是$\Theta(n^2)$，似乎与暴力没什么区别。
但是长度连续的一串卷积除了一个个枚举外，还可以用FFT加以优化。
假设要求卷积$\sum^{n-1}_{i=1}{a_i*b_{n-i}}$（我喜欢称为长度为$n-1$的卷积）
那么构造两个多项式：
那么将两个式子相乘前n项的系数分别对应长度为$1$~$n$的卷积的值。
那么上面那个卷积的值即为$A_n*B_n$的第$n-1$项。
此时时间复杂度降为$\Theta(n\log_2n)$。
回到题目，设:
则$E_i=L_{i-1}-R_{n-i}$。
上代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;
const double pi=acos(-1);
inline int read()
{
int kkk=0,x=1;
char c=getchar();
while((c<'0' || c>'9') && c!='-')
c=getchar();
if(c=='-')
c=getchar(),x=-1;
while(c>='0' && c<='9')
kkk=(kkk<<3)+(kkk<<1)+(c-'0'),c=getchar();
return kkk*x;
}
struct complex
{
double x,y;
complex(double xx=0,double yy=0){x=xx,y=yy;}
}a[300001],b[300001],c[300001];
complex operator +(complex x,complex y){return complex(x.x+y.x,x.y+y.y);}
complex operator -(complex x,complex y){return complex(x.x-y.x,x.y-y.y);}
complex operator *(complex x,complex y){return complex(x.x*y.x-x.y*y.y,x.y*y.x+x.x*y.y);}
int n,lim,LOG,zone[300001];
inline void FFT(complex *A,int type)
{
for(register int i=0;i<lim;++i)
if(zone[i]>i)
swap(A[i],A[zone[i]]);
for(register int len=1;len<lim;len*=2)
{
complex wn(cos(pi/len),type*sin(pi/len));
for(register int bj=0;bj<lim;bj+=2*len)
{
complex w(1,0);
for(register int i=0;i<len;++i,w=w*wn)
{
complex A0=A[bj+i],A1=w*A[bj+i+len];
A[bj+i]=A0+A1;
A[bj+i+len]=A0-A1;
}
}
}
}
int main()
{
n=read();
LOG=ceil(log2(n*2));
lim=(1<<LOG);
for(register int i=0;i<lim;++i)
zone[i]=((zone[i>>1]>>1) | ((i&1)<<(LOG-1)));
for(register int i=0;i<n;++i)
scanf("%lf",&a[i].x),c[n-i-1].x=a[i].x;
for(register int i=1;i<=n;++i)
b[i-1].x=(double)1.0/i/i;
FFT(a,1);
FFT(b,1);
FFT(c,1);
for(register int i=0;i<lim;++i)
{
a[i]=a[i]*b[i];
c[i]=c[i]*b[i];
}
FFT(a,-1);
FFT(c,-1);
for(register int i=0;i<n;++i)
{
double ans=0;
if(i!=0)
ans+=a[i-1].x/lim;
if(i!=n-1)
ans-=c[n-i-2].x/lim;
printf("%.3lf\n",ans);
}
return 0;
}
|