\(X\) の前から \(i\) 番目の桁を \(x_i\) 、前から \(i\) 番目の桁まで考えたときの答えを \(a_i\) とします。

\(x_{i-1}\) までを固定すると、寄与を考えることで \(a_i\) は \(x_i\) の一次関数であることが分かります。具体的には、

• \(1\) 次の係数は（最後にどこで区切れたかを考えて） \(s_i:=1+\displaystyle\sum_{j<i} a_j\)
• 定数項は（\(x_i=0\) の場合を考えて） \(10a_{i-1}\)

であることから \(a_i=10a_{i-1} + x_i s_i\) です。 累積和を適切に管理することで \(O(N)\) で計算できます。

AC コード （PyPy3）