遷移が線形なので，行列積で書ける． + を置いたときに，+ より左にある項の和を \(t\), 今計算中の項を \(x\) とおく． 遷移は，
- \(s_{i}\) の直前に + を置く場合：
\(t \rightarrow t + x\), \(x \rightarrow s_{i}\), \(1 \rightarrow 1\) となるので，基を \([t,x,1]\) としたときの遷移の行列は \[a_{i} := \left(\matrix{ 1 &0 &0 \\ 1 &0 &0 \\ 0 &s_{i} &1 }\right) \]. - \(s_{i}\) の直前に + を置かない場合：
\(t \rightarrow t\), \(x \rightarrow 10x + s_{i}\), \(1 \rightarrow 1\) となるので，基を \([t,x,1]\) としたときの遷移の行列は \[b_{i} := \left(\matrix{ 1 &0 &0 \\ 0 &10 &0 \\ 0 &s_{i} &1 }\right) \]
実装
\(s_{-1} = 0\)，\(s_{-1}\) と \(s_{0}\) の間に + がある とする． 答えは \[\left(\matrix{ 1 & 1 & 0 }\right) a_{0} (a_{1} + b_{1}) \cdots (a_{n-1} + b_{n-1}) \left(\matrix{ 1 \\ 1 \\ 0 }\right). \] 最初の項が \(a_{0}\) のみであるのは，\(s_{-1}\) と \(s_{0}\) の間は必ず + が入っているから． 最後に \(\left(\matrix{ 1 \\ 1 \\ 0 }\right)\) を掛けているのは，\(t,x\) の両方の和が答えだから． \(x\) はまだ保留して計上してないので，最後に計上するため．
補足
\(s_{n} = 0\)，\(s_{n-1}\) と \(s_{n}\) の間に + がある とすれば， \[\left(\matrix{ 1 & 1 & 0 }\right) a_{0} (a_{1} + b_{1}) \cdots (a_{n-1} + b_{n-1}) a_{n} \left(\matrix{ 1 \\ 0 \\ 0 }\right)\] でも答えは求まる．
\(a_{0}, a_{n}\) の部分に \(b_{0}, b_{n}\) が出てこないのは， 最初と最後は選択の余地がないから． 他の場所は，+ をつけるか何もしないかの 2つ選択肢があるから 2項が現れている．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
