题解 P6796 【「StOI-2」好多表达式】

· · 题解

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

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

数字 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的优秀子序列。都是这个思想。