题意：给定一个由数字和加号和乘号组成的字符串，求出 \(\sum s(i,j)\)。其中 \(s(i,j)\) 表示 \(i\) 到 \(j\) 字符组成的表达式的值。
考虑 \(\text{dp}\)。
设 \(dp_{i}\) 表示以 \(i\) 为起点的所有表达式的值之和。那么我们考虑以一些加号作为分界点来转移。
假设 \(i\) 右边最近的加号的位置为 \(pos1\)，并且 \(i\) 到 \(pos1-1\) 组成的数为 \(num1\)，设 \(cnt_i\) 表示在 \(i\) 之后可能有多少个右端点（即有多少个数字）。那么终点在 \(pos1\) 后面的所有情况的和为 \(num1 \times cnt_i + dp_{pos1+1}\)。
接下来考虑右端点在 \(pos1\) 前面的情况，这一定是一个连乘的形式，设 \(pos2\) 表示 \(i\) 右边最近的乘号，\(num\) 表示 \(i\) 到 \(pos2-1\) 组成的数，这也同样可以 \(\text{dp}\)。
设 \(s0_i\) 表示从 \(i\) 开始的所有数之和（直到有符号），\(s1_i\) 表示从 \(i\) 开始的所有连乘之和（直到有加号）。那么有转移：
\[s0_i=s0_{i+1}+a_i \times (10^0+10^1+\dots+10^{pos2-i-1}) \]\[s1_i=num \times s1_{pos2+1}+s0_i \]最终 \(dp_i\) 的值则为 \(dp_{pos1+1} + num1 \times cnt_i + s1_i\)。
答案即为 \(\sum_{i=1}^{n} dp_i\)。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e6 + 10;
const int mod = 998244353;
int dp[MAXN],sum[MAXN],p[MAXN],cnt[MAXN],n,ans,pos1,pos2,s0[MAXN],s1[MAXN],num,num1;
char a[MAXN];
bool flag = 1;
signed main()
{
cin >> (a + 1);
n = strlen(a + 1),p[0] = 1;
pos1 = pos2 = n + 1;
sum[0] = 1;
for(int i = 1;i <= n;i++)
{
p[i] = p[i - 1] * 10 % mod;
sum[i] = (sum[i - 1] + p[i]) % mod;
}
for(int i = n;i >= 1;i--) cnt[i] = cnt[i + 1] + (a[i] >= '0' && a[i] <= '9');
num1 = 1;
for(int i = n;i >= 1;i--)
{
if(a[i] == '+')
{
pos1 = i;
num = 0;
num1 = 1;
flag = 1;
}
else if(a[i] == '*')
{
pos2 = i;
num1 = (num1 * num) % mod;
num = 0;
flag = 0;
}
else
{
num = (num + (a[i] - '0') * p[min(pos1,pos2) - i - 1]) % mod;
// cout << "i = " << i << " num = " << num << " num1 = " << num1 << endl;
s0[i] = (s0[i + 1] + (a[i] - '0') * sum[min(pos2,pos1) - i - 1] % mod) % mod;
s1[i] = ((flag == 0 ? num * s1[pos2 + 1] % mod : 0) + s0[i]) % mod;
dp[i] = (dp[pos1 + 1] + s1[i] + num * num1 % mod * cnt[pos1] % mod) % mod;
// cout << "s0 = " << s0[i] << " s1 = " << s1[i] << " dp = " << dp[i] << endl;
}
}
for(int i = 1;i <= n;i++)
{
ans = (ans + dp[i]) % mod;
}
cout << ans;
return 0;
}