公式解説では \(U_i = \text{parse}(S[i\dots N])\) (\(i \in [0, N]\)) とする方針で書かれていますが、\(V_i = \text{parse}(S[0\dots i])\) (\(i \in [0, N]\)) とする方針を書きます。

※ \(S\) の添字は 0-indexed とし、\(S[i\dots j]\) は終端を含まずに \((S_i, S_{i+1}, \dots, S_{j-1})\) を表すとします。

まず、\(V_0 = 0\) および \(V_{i+1} = V_i \cdot 10 + S_i\) (\(i \in [0, n)\)) です。また、\(\text{parse}(S[l\dots r]) = V_r - V_l\cdot 10^{r-l}\) と表せます。

よって、\(V_r-V_l\cdot 10^{r-l}\equiv 0\pmod{p}\) となるペア \((l, r)\) を数えればよいです。\(10^{-1}\bmod p\) が存在する (i.e. \(\gcd(10, p) = 1\)) 下で、変数分離して以下のようにできます。

\[ V_l\cdot 10^{-l} \equiv V_r\cdot 10^{-r} \pmod{p}. \]

なので、\(W_i = V_i\cdot 10^{-i}\) として、各 \(i\) に対して \(\{j \mid j\in[0, i)\wedge W_i\equiv W_j\pmod{p}\}\) のサイズを数えて合計すればよいです（これは公式解説同様、今までの出現回数を覚えておけば ok）。

\(\gcd(10, p) \gt 1\) の場合は別途処理します。

以上より、\(O(N\log(N)+\log(P))\) time や \(O(N+P)\) time などで解けます。

実装例：C++, Rust

区間 \([l, r)\) に対する条件を \(f(l) = g(r)\) と表せるように変形する（今回は \(f=g\)）のはありがちですね。

See also: https://kmyk.github.io/blog/blog/2020/11/04/separation-of-variables/