专栏文章

爱好题解

lleather_handbag
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mkhw0swa
此快照首次捕获于
2026/01/17 13:49
上个月
此快照最后确认于
2026/01/17 13:49
上个月
查看原文

官解

Problem

给定一个长度为 NN 的序列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,求以下表达式的值：
∑k=1n{ak+∑i=1k−1∑j=1k−1[(∏l=1ial 2 i−l)(∏l=1jal 2 j−l)]}\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 的性质：
∑a=lr∑b=lr[f(a)f(b)]=[∑a=lrf(a)][∑b=lrf(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]
对于第二个 ∑\sum，f(a)f(a) 可视作常量，于是便可以提出来，得到
∑a=lr∑b=lr[f(a)f(b)]=∑a=lr[f(a)∑b=lrf(b)]\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 来说，∑b=lrf(b)\sum_{b=l}^{r}f(b) 又可视作常量，提出来得到
∑a=lr∑b=lr[f(a)f(b)]=[∑a=lrf(a)][∑b=lrf(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)=∏l=1xal2x−lf(x)=\prod_{l=1}^{x}a_l^{2^{x-l}}
所以原式即为
∑k=1n[ak+∑i=1k−1∑j=1k−1f(i)f(j)]\sum_{k=1}^{n}\bigg[a_k+\sum_{i=1}^{k-1}\sum_{j=1}^{k-1}f(i)f(j)\bigg]
由 ∑\sum 的性质（已证明）可得原式为
∑k=1n{ak+[∑i=1k−1f(i)][∑j=1k−1f(j)]}\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\}
由于中括号中的式子相同，所以原式得
∑k=1n{ak+[∑i=1k−1f(i)]2}\sum_{k=1}^{n}\Bigg\{a_k+\bigg[\sum_{i=1}^{k-1}f(i)\bigg]^2\Bigg\}
如果知道了 f(i)f(i) 的值，中括号和大括号就可以通过前缀和来计算，所以现在再来观察 f(i)f(i) 部分。考虑进行递推，注意到
f(i)=∏l=1ial2i−l=ai2i−i×∏l=1i−1(al2i−1−l)2=ai×f(i−1)2\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)=1f(0)=1。
自此，这道题就没有了难点，使用基本前缀和即可完成。

Code

CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...