ABC158 E. Divisible Substring

問題

0から9までの数字からなる長さNの文字列が与えられる。
この文字列の空出ない連続する部分文字列を考える。
部分文字列を数字として見たときに、素数Pで割り切れるものの個数を求めよ。
ただし、0から始まるものでもよく、それらは異なる数字とみなす。

制約

• 1 <= N <= 2 * 10^5
• 2 <= P <= 10000
• Pは素数

解法

元の文字列の数字は、
S[0] * 10^(N-1) + S[1] * 10^(N-2) + ... + S[N-1] * 10^0
のように考えることができる。
これのmod Pは、各桁について「S[i] * 10^(N-i-1)」のmod Pを足したものに相当する。

なので、ある部分文字列を考えるというのは、iからjまでの↑の和のmod Pで求められ、それが0になるようなものの個数を求める問題になっている。

単純に考えるとO(N^2)になってしまうが、低い桁からの累積和を考えて、iまでの累積和sum[i]と同じ値が0～i-1までに何個出ているか？を考えれば、その地点からiまでの和は0なので、求められる。
また、sum[i]自体が0の場合は、それ単独でmod P=0になるので、+1する。

ただし、コーナーケースとして、P=2,5のときは、「S[i] * 10^(N-i-1)」がN-i-1>0だと10の倍数でPで割り切れてしまうため、答えも0になってしまう。
P=2,5のときは、Pが小さいのでO(N*P)のdpで解くか、2,5で割り切れるかは最後の桁がPで割り切れるかで決まるので、S[i] mod P = 0ならi+1を加える処理でO(N)で求められる。