洛谷 P3338 【ZJOI2014】力/BZOJ 3527 力 题解

洛谷 P3338 【ZJOI2014】力/BZOJ 3527 力 题解

题意

给定一个正整数$n(1\leq n\leq 10^5)$,以及有$n$个元素的浮点数序列$q(0<q_i<10^9)$.要求对于所有的$i\in [1,n]$,输出

$E_j=\sum_{i=1}^{j-1}\frac{q_i\times q_j}{(i-j)^2}-\sum_{i=j+1}^n\frac{q_i\times q_j}{(i-j)^2}$

注:当你输出的答案与标准答案相差不超过$10^{-2}$时,即视为答案正确.

题解

显然,暴力是行不通的,所以考虑使用$FFT$进行卷积来处理.
首先考虑序列能进行卷积所要满足的条件:

$c_i=\sum_{j=0}^ia_j\times b_{n-j}$

所以我们必须要把原式变得好看一点才能进行卷积.
我们不妨令$a_i=q_i,b_i=\frac{1}{i^2}$,那么可以对原式进行一下变形:

$E_j=\sum_{i=1}^{j-1}\frac{q_i\times q_j}{(i-j)^2}-\sum_{i=j+1}^n\frac{q_i\times q_j}{(i-j)^2} =\sum_{i=1}^{j-1}a_ib_{j-i}-\sum_{i=j+1}^{n}a_ib_{i-j}$

那么当我们令$a_0=b_0=0$时,不难发现将其变形为

$\sum_{i=0}^{j}a_ib_{j-i}-\sum_{i=j}^{n}a_ib_{i-j}$

依然是正确的.此时前一项已经满足卷积的要求了,我们单独处理后一项.
不难证明一下变形这正确的:

$\sum_{i=j}^{n}a_ib_{i-j}=\sum_{i=0}^{n-j}a_{i+j}b_i$

接下来运用反转的思想,令$c_i=a_{n-i}$,那么可变形为

$\sum_{i=0}^{n-j}a_{i+j}b_i=\sum_{i=0}^{n-j}c_{n-i-j}b_i$

这样一来,第二个式子也满足卷积的条件啦!
所以我们对$a$和$b$跑一次$FFT$,再对$b$和$c$跑一次$FFT$,设得到的两个序列为$p$和$q$,那么答案就为$E_j=p_j-q_{n-j}$,套上$FFT$的板子即可.

Code

#include<bits/stdc++.h>
using namespace std;
#define M_PI 3.141592653589793
typedef complex<long double> comp;
const int MAXN=100010;
const comp I(0,1);
int n;
comp a[MAXN*4];
comp b[MAXN*4];
inline void change(comp *f,int len)
{
    for(int i=1,j=len>>1;i<len-1;i++)
    {
        if(i<j) swap(f[i],f[j]);
        int k=len>>1;
        while(j>=k)
        {
            j-=k;
            k>>=1;
        }
        if(j<k) j+=k;
    }
}
inline void FFT(comp *f,int len,int rev)
{
    change(f,len);
    for(int h=2;h<=len;h<<=1)
    {
        comp wn=exp(I*(long double)(2*M_PI/h*rev));
        for(int i=0;i<len;i+=h)
        {
            comp cur(1,0);
            for(int j=i;j<i+(h>>1);j++)
            {
                comp p=f[j],q=cur*f[j+(h>>1)];
                f[j]=p+q,f[j+(h>>1)]=p-q;
                cur*=wn;
            }
        }
    }
    if(rev==-1)
    for(int i=0;i<len;i++) f[i]/=len;
}
comp c[MAXN*4];
int len;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        long double x;
        scanf("%Lf",&x);
        a[i]={x,0};
    }
    for(int i=1;i<n;i++) b[i]=1.0/(1.0*(long double)i*(long double)i);
    for(int i=0;i<n;i++) c[i]=a[n-i];
    len=1;
    while(len<=2*n) len<<=1;
    FFT(a,len,1),FFT(b,len,1),FFT(c,len,1);
    for(int i=0;i<len;i++) c[i]*=b[i],b[i]*=a[i];
    FFT(b,len,-1),FFT(c,len,-1);
    for(int i=0;i<n;i++) printf("%.3Lf\n",real(b[i]-c[n-i]));
	return 0;
}

后记

本人第一次做$FFT$练习题,感觉还算顺利(除了悄悄地看了两眼题解的解题思路)比较惨的是之前π精度不够结果居然一片红,所有点都差零点几的样子QAQ所幸后面改过来之后一边就过了吧……最后我一定要吐槽一句,数学题的$LaTeX$真难写……搞了半天才搞定QAQ