https://atcoder.jp/contests/abc158/tasks/abc158_e
$N$桁の整数$S$が与えられる($N\leq 2\times10^5$)。この整数の$N(N-1)/2$個の部分文字列のうち、素数$P$で割り切れるものの数を出力せよ。
整数$S$の$i$桁目から$j-1$桁目までを10進数として解釈したものを$S[i,j)$と表す。
ここで、$S[i, j)=\frac{S[i, N)-S[j, N)}{10^{j-i}}$であるが、$P$が10と互いに素であれば、$\frac{S[i, N)-S[j, N)}{10^{j-i}}$が$P$で割り切れるとき$S[i, N)-S[j, N)$も必ず$P$で割り切れる(逆も成り立つ)。これは、$\frac{S[i, N)-S[j, N)}{10^{j-i}}$が$\mod P$で0でない場合には10をいくらかけても0にならないためである(0のときは、10をいくらかけても当然0となる)。よって、$S[i,N)\mod P$のなかで同じものがいくつあるかを数えて、同じものが$m$個あるときに$_mC_2$を足し合わせたものが答えとなる。
10と$P$が互いに素ではないとき、つまり$P=2, 5$の場合には、部分文字列の末尾だけをみれば$P$で割り切れるかがわかるので、O($N$)でこの問題が解ける。
普通に難しくないか……？惜しかったという感じもしない。本番ではあまりにわからないのでO($NP$)のDPを頑張って高速化しようとしていた。