自动搬运

查看原文

来自洛谷，原作者为

	lndjy 退役oier，偶尔参与比赛出题，tag是我另一个身份，有人认识吗（）

搬运于2025-08-24 22:24:05，当前版本为作者最后更新于2020-08-28 07:14:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，所有子表达式运算值之和 的意思就是所有区间的运算和，这样表述下文方便。

考虑在一个表达式后面，加上一个符号和一个数字，这对答案有什么贡献。

数字 $a_i$ 对答案有贡献的区间是 $[1,i],[2,i]...[i,i]$。其他的区间前面计算好了，不需要考虑。

先考虑没有加号的情况。对于前面的每个区间，都是乘了 $a_i$，根据乘法分配律，也就是对前面的积乘 $a_i$。然后加上 $[i,i]$ 本身，也就是 $a_i$。

然后考虑加号有什么影响。

首先，就加号本身而言，是对前面的所有区间产生了 $+a_i$ 的贡献，这个很好理解。然后在后面的计算中，碰到加号时，对最近一个加号以前的数字没有乘的贡献，但是有加上目前这段连续乘的贡献。

用两个变量模拟当前连续乘乘和累加的结果，然后按照上文计算贡献即可。

代码：

#include<iostream>
#define int long long
using namespace std;
const int N=1e5+5,p=998244353;
int a[N],n;
char c[N];
signed main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	cin>>a[i]>>c[i];
	cin>>a[n];
	bool flag=0;
	int mul=1,sum=0,ans=0;
	for(int i=1;i<=n;i++)
	{
		if(flag) mul=(mul*a[i]+a[i])%p;
		else mul=(i*a[i])%p;
		flag=1;
		ans=(ans+mul+sum)%p;
		if(c[i]=='+')
		{
			flag=0;
			sum=(sum+mul)%p;
		}
	}
	cout<<ans;
	return 0;
}

题外话:考虑加上一步有什么贡献，这是一个很常见的套路。CSP的括号树，NOIO的优秀子序列。都是这个思想。