題意を再掲します。

• 以下のプログラムに文字列 \(S\) を入力した際の出力を求めよ。

S = input()
MOD = 998244353
ans = 0
for i in range(len(S)):
    for j in range(i, len(S)):
        if S[i].isdigit() and S[j].isdigit():
            ans += eval(S[i : j + 1])
print(ans % MOD)

• 主な制約
  • \(|S| \leq 10^6\)
  • \(S\) の各文字は 123456789+* のいずれかである。

---

数字だけなら

\(S\) のすべての文字が数字であるとします。例えば \(S =\) 1234 としましょう。数字 2 が \(\mathrm{eval}(S_{i..j})\) に寄与する場合は以下の通りです。

• \(12 = 1 \times 10 + \underline{2 \times 1}\)
• \(123 = 1 \times 100 + \underline{2 \times 10} + 3 \times 1\)
• \(1234 = 1 \times 1000 + \underline{2 \times 100} + 3 \times 10 + 4 \times 1\)
• \(2 = \underline{2 \times 1}\)
• \(23 = \underline{2 \times 10} + 3 \times 1\)
• \(234 = \underline{2 \times 100} + 3 \times 10 + 4 \times 1\)

以上を合計すると、\(2\) は答えに \(222\) 回加算されます。他の数字も同様に考えると、答えは \(1 \times 1111 + 2 \times 222 + 3 \times 33 + 4 \times 4\) です。

ここで、各数字の左側と右側を独立に考えられることに注意します。例えば、\(S =\) 12 とすると \(2\) が答えに加算される回数は \(2\) 回、\(S =\) 234 とすると \(111\) 回で、\(S =\) 1234 の場合の回数はこれらの積です。

数字と +

\(S\) のすべての文字が数字または + であるとします。例えば \(S =\) 99+1234+999 としましょう。数字 2 が \(\mathrm{eval}(S_{i..j})\) に寄与する場合は以下の通りです。

\(\mathrm{eval}(S_{i..j})\)	：	寄与回数
\(99+12\)	：	\(1\)
\(99+123\)	：	\(10\)
\(99+1234\)	：	\(100\)
\(99+1234+9\)	：	\(100\)
\(99+1234+99\)	：	\(100\)
\(99+1234+999\)	：	\(100\)
\(9+12\)	：	\(1\)
\(9+123\)	：	\(10\)
\(9+1234\)	：	\(100\)
\(9+1234+9\)	：	\(100\)
\(9+1234+99\)	：	\(100\)
\(9+1234+999\)	：	\(100\)
\(12\)	：	\(1\)
\(123\)	：	\(10\)
\(1234\)	：	\(100\)
\(1234+9\)	：	\(100\)
\(1234+99\)	：	\(100\)
\(1234+999\)	：	\(100\)
\(2\)	：	\(1\)
\(23\)	：	\(10\)
\(234\)	：	\(100\)
\(234+9\)	：	\(100\)
\(234+99\)	：	\(100\)
\(234+999\)	：	\(100\)

以上を合計すると、\(2\) は答えに \(4 \times 411\) 回加算されます。他の数字も同様に考えれば答えが求まります。

ここでも、各数字の左側と右側を独立に考えられることに注意します。例えば、\(S =\) 99+12 とすると \(2\) が答えに加算される回数は \(4\) 回、\(S =\) 234+999 とすると \(411\) 回で、\(S =\) 99+1234+999 の場合の回数はこれらの積です。

数字と + と *

\(S\) のすべての文字が数字または + または * であるとします（元の問題）。乗算が加わると、これまでの考え方を修正しなければなりません。

例えば、\(S =\) 2*3 のときの答えは \(2 + 2 \times 3 + 3\) ですが、これまでと同様に 2 の寄与と 3 の寄与を考えて足すと、\(2 \times 3\) を二度数えてしまいます。ここでは、乗算の結果は最も右の要素による寄与として扱いましょう。\(S =\) 2*3 のときは、\(2 \times 3\) では \(3\) が \(2\) 回足されると考え、答えに \(2\) が足される回数は \(1\) 回、\(3\) が足される回数は \(2 + 1 = 3\) 回とします。

このように考えれば、これまでと同様の計算を行えます。例えば \(S =\) 99+345*456*567*12 としましょう。数字 2 が \(\mathrm{eval}(S_{i..j})\) に寄与する場合は以下の通りです。

$\mathrm{eval}(S_{i..j})$	：	寄与回数
$99+345\times456\times567\times12$	：	$345\times456\times567$
$9+345\times456\times567\times12$	：	$345\times456\times567$
$345\times456\times567\times12$	：	$345\times456\times567$
$45\times456\times567\times12$	：	$45\times456\times567$
$5\times456\times567\times12$	：	$5\times456\times567$
$456\times567\times12$	：	$456\times567$
$56\times567\times12$	：	$56\times567$
$6\times567\times12$	：	$6\times567$
$567\times12$	：	$567$
$67\times12$	：	$67$
$7\times12$	：	$7$
$12$	：	$1$
$2$	：	$1$

以上を合計すると、\(2\) は答えに \(2 \times 345 \times 456 \times 567 + (345 + 45 + 5) \times 456 \times 567 + (456 + 56 + 6) \times 567 + (567 + 67 + 7) + 2\) 回加算されます。\(S\) の末尾以外の数字については、これまでと同様にその数字の左側と右側を独立に考えることができます。ここで、乗算の結果は最も右の要素による寄与としているため、ある数字の右側に現れる最初の演算子が * であるなら、その * を跨ぐ場合は考えません。

同じ計算の繰り返しを省けば、線形時間で答えを計算できます。

実装例（Python）

S = input()
MOD = 998244353

p10 = [1] * (len(S) + 1)
for i in range(len(S)):
    p10[i + 1] = p10[i] * 10 % MOD
q10 = [0] * (len(S) + 1)
for i in range(len(S)):
    q10[i + 1] = (q10[i] + p10[i]) % MOD

ans = 0
sofar, remain = 0, len(list(filter(lambda c: c.isdigit(), S)))
for t in S.split("+"):
    p, q = 1, 0
    ts = t.split("*")
    for i in range(len(ts)):
        u = ts[i]
        remain -= len(u)
        v, w = 0, 0
        for j in range(len(u) - 1, -1, -1):
            l = j + 1 + q + p * sofar
            r = q10[len(u) - j]
            if i == len(ts) - 1:
                r += p10[len(u) - 1 - j] * remain
            ans = (ans + int(u[j]) * l * r) % MOD
            v = (v + int(u[j]) * p10[len(u) - 1 - j]) % MOD
            w = (w + v) % MOD
        p = p * v % MOD
        q = (q * v + w) % MOD
    sofar += len(t) - t.count("*")
print(ans)