ABC224F 遷移が線形なので,行列積で書ける. + を置いたときに,+ より左にある項の和を \(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}\) の直前に + を置か…