0%

「ZJOI2014」力

发表于 更新于 阅读次数： Valine：

给出n个数\(q_i\)，给出\(F_j\)的定义如下： \[ F_j = \sum_{i<j}\frac{q_i q_j}{(i-j)^2 }-\sum_{i>j}\frac{q_i q_j}{(i-j)^2 } \]

令\(E_i=\frac{F_i}{q_i}\)，求\(E_i\)

\[ E_j=\sum_{i<j}\frac{q_i}{(i-j)^2 }-\sum_{i>j}\frac{q_i}{(i-j)^2 } \]

设\(f[i]=q[i],g[i]=\frac{1}{i^2}\)

则 \[ E_j=\sum\limits_{i<j}f[i]g[j-i]-\sum\limits_{i>j}f[i]g[i-j]\\ E_j=\sum\limits_{i=1}^{j-1}f[i]g[j-i]-\sum\limits_{i=j+1}^nf[i]g[i-j] \] 设\(f'[i]=f[n-i+1]\)

则 \[ E_j=\sum\limits_{i=1}^{j-1}f[i]g[j-i]-\sum\limits_{i=1}^{n-j}f'[i]g[j-i] \] 直接卷积就好

code:

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
#include<bits/stdc++.h>
using namespace std;
double const pi=acos(-1);
struct comp
{
    double r=0,i=0;
    friend comp operator +(const comp &x,const comp &y){return (comp){x.r+y.r,x.i+y.i};}
    friend comp operator -(const comp &x,const comp &y){return (comp){x.r-y.r,x.i-y.i};}
    friend comp operator *(const comp &x,const comp &y){return (comp){x.r*y.r-x.i*y.i,x.r*y.i+x.i*y.r};}
}q[400005],qq[400005],f[400005];
int r[400005];
void getrev(int n)
{
    for(int i=1;i<n;i++)r[i]=(r[i>>1]>>1)+((i&1)?(n>>1):0);
}
void fft(comp* f,int n,int op)
{
    for(int i=1;i<n;i++)if(i<r[i])swap(f[i],f[r[i]]);
    for(int len=2;len<=n;len<<=1)
    {
        int q=len>>1;
        comp wn={cos(2*pi/len),op*sin(2*pi/len)};
        for(int i=0;i<n;i+=len)
        {
            comp w={1,0};
            for(int j=i;j<i+q;++j)
            {
                comp d=f[j+q]*w;
                f[j+q]=f[j]-d;
                f[j]=f[j]+d;
                w=w*wn;
            }
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf",&q[i].r),qq[n-i+1].r=q[i].r;
    for(int i=1;i<=n;i++)f[i].r=(((double)1.0)/(double)i/(double)i);
    int len=1;
    while(len<(n<<1))len<<=1;
    getrev(len);
    fft(q,len,1),fft(qq,len,1),fft(f,len,1);
    for(int i=0;i<len;i++)q[i]=q[i]*f[i],qq[i]=qq[i]*f[i];
    fft(q,len,-1),fft(qq,len,-1);
    for(int i=1;i<=n;i++)printf("%.5lf\n",(q[i].r-qq[n-i+1].r)/len);
    return 0;
}