爱好题解

· · 题解

官解

Problem

给定一个长度为 N 的序列 a_1,a_2,\cdots,a_n,求以下表达式的值：

\sum_{k=1}^{n}\left\{a_k+\sum_{i=1}^{k-1}\sum_{j=1}^{k-1}\Biggl[\Biggl(\prod_{l=1}^{i}a_{l}^{\,2^{\,i-l}}\Biggr)\Biggl(\prod_{l=1}^{j}a_{l}^{\,2^{\,j-l}}\Biggr)\Biggr]\right\}

Solution

先感性证明一个 \sum 的性质：

\sum_{a=l}^{r}\sum_{b=l}^{r}\bigg[f(a)f(b)\bigg]=\bigg[\sum_{a=l}^{r}f(a)\bigg]\bigg[\sum_{b=l}^{r}f(b)\bigg]

对于第二个 \sum，f(a) 可视作常量，于是便可以提出来，得到

\sum_{a=l}^{r}\sum_{b=l}^{r}\bigg[f(a)f(b)\bigg]=\sum_{a=l}^{r}\bigg[f(a)\sum_{b=l}^{r}f(b)\bigg]

而对第一个 \sum 来说，\sum_{b=l}^{r}f(b) 又可视作常量，提出来得到

\sum_{a=l}^{r}\sum_{b=l}^{r}\bigg[f(a)f(b)\bigg]=\bigg[\sum_{a=l}^{r}f(a)\bigg]\bigg[\sum_{b=l}^{r}f(b)\bigg]

证毕。

原式

观察到原式中有重复部分，所以我们考虑构造函数，令

f(x)=\prod_{l=1}^{x}a_l^{2^{x-l}}

所以原式即为

\sum_{k=1}^{n}\bigg[a_k+\sum_{i=1}^{k-1}\sum_{j=1}^{k-1}f(i)f(j)\bigg]

由 \sum 的性质（已证明）可得原式为

\sum_{k=1}^{n}\Bigg\{a_k+\bigg[\sum_{i=1}^{k-1}f(i)\bigg]\bigg[\sum_{j=1}^{k-1}f(j)\bigg]\Bigg\}

由于中括号中的式子相同，所以原式得

\sum_{k=1}^{n}\Bigg\{a_k+\bigg[\sum_{i=1}^{k-1}f(i)\bigg]^2\Bigg\}

如果知道了 f(i) 的值，中括号和大括号就可以通过前缀和来计算，所以现在再来观察 f(i) 部分。考虑进行递推，注意到

\begin{aligned} f(i)=&\prod_{l=1}^{i}a_l^{2^{i-l}}\\ =&a_i^{2^{i-i}} \times \prod_{l=1}^{i-1}({a_l^{2^{i-1-l}})^2}\\ =&a_i\times f(i-1)^2 \end{aligned}

于是我们就得到了递推式，边界条件为 f(0)=1。

自此，这道题就没有了难点，使用基本前缀和即可完成。

Code

const int N=5e6+99,mod=1e9+7;
inline int read(){
    int x=0;
    bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x;
}
int n;
signed main(){
    n=read();
    int mul=1;
    int ans=0;
    int fsum=0;
    for(int i=1;i<=n;i++){
        int x;
        x=read();
        mul=mul*mul%mod*x%mod;
        ans=(ans+x+fsum*fsum%mod)%mod;
        fsum=(fsum+mul)%mod;
    }
    cout<<ans<<endl;
    return 0;
}