数式の変形に頼らずなるだけ直観的に解く方法について、例を用いて解説します。

例えば \(X = 2345\) の 3 文字目まで見終わったとき、その時点での \(f(S)\) の総和は

\[ 234 + 2 \times 34 + 23 \times 4 + 2 \times 3 \times 4 \]

ですが、これを

• \(1\) 個の \(234\)
• \(2\) 個の \(34\)
• \(23\) 個の \(4\)
• \((2 \times 3)\) 個の \(4\)

の和と解釈し、個数の総和 \(c[3]\) と \(f(S)\) の総和 \(s[3]\) のみを記録しておきます。

4 文字目まで見たときの個数の総和 \(c[4]\) と \(f(S)\) の総和 \(s[4]\) は次のように求められます。

• 5 を単独で用いる場合は \(5\) が \(s[3]\) 個増えるので、\(c[4]\) への寄与は \(s[3]\)、\(s[4]\) への寄与は \(5 s[3]\) となります。

• 5 を繋げて用いる場合はいままでの数全てが \(10\) 倍された上 \(5\) を足されるので、\(c[4]\) への寄与は \(c[3]\)、\(s[4]\) への寄与は \(10 s[3] + 5 c[3]\) となります。

具体的な遷移はこれらを合わせた

• \(c[4] = s[3] + c[3]\)
• \(s[4] = 5 s[3] + (10 s[3] + 5 c[3])\)

となります。

1 個の 0 がある状態（\(c[0] = 1, s[0] = 0\)）を初期状態として同様の遷移を繰り返すことで \(O(N)\) で答えが求まります。

提出コード（C++）