ABC158に参加した。自分用メモ。

A	B	C	D	E	F
o	o	o	o	x	x

A~Dは特に問題なく解けた。

E-Divisible Substring

ある非負整数を表す文字列と素数Pが与えられ、その文字列の連続する部分文字列が表す数でPの倍数となっているものの個数を数える問題。 連続する部分文字列の個数は、文字列の長さをNとして$N(N+1)/2$となるので、すべての部分文字列について全探索すると制限時間に間に合わない。

文字列が表す数の大きさが($1\le N \le 2\times 10^5$)だと勘違いして、素数の倍数を前計算してローリングハッシュ法で答えを求めるなどしてしまった。そもそもこの制約なら全探索で間に合う。A~D問題くらいだと考察ほとんどいらない場合が多いけど、Eあたりからは必要になってくるので、考察をすっぽぬかす癖をなおしたい。

考察

だいたい最初は解説と同じだけど、累積和求めたあとに実際数えるとこがいまいちわからなかったので、書き残しておく。

まず連続する部分文字列の表す数が条件を満たす場合の性質を調べたい。以降、連続する部分文字列を単に部分文字列と書くことにする。 与えられた文字列が表す数は、右端から数えてi番目の数を$a_i$とすると、

$$a_N\times 10^{N-1} + a_{i-1}\times 10^{i-2} + \cdots + a_2\times 10^{1} + a_1\times 10^{0}$$

と表すことができるので、l番目からr番目($l \ge r$)の文字からなる数は、

$$\frac{\sum_{k = r}^{l} a_{k}\times 10^{k-1}}{10^{r-1}}$$

で表される。この数が与えられた素数$p$で割り切れるかどうかを知りたい。

$p$が10と互いに素でないとき、これを満たす素数$p$は2か5である。$p$が2か5であれば、部分文字列の右端の数が2か5で割り切れれば、その部分文字列が表す数が$p$で割り切れるかわかるので、$O(N)$で答えを求められる。

$p$が10と互いに素である場合について考える。

$$\begin{eqnarray} & & \frac{\sum_{k = r}^{l} a_{k}\times 10^{k-1}}{10^{r-1}} \equiv 0 \pmod P \\ & \Leftrightarrow & \sum_{k = r}^{l} a_{k}\times 10^{k-1} \equiv 0 \pmod P \end{eqnarray}$$

ここで解説と同じように、

$$C_{i} := 文字列の右端からi番目までの累積和 \bmod P$$

と定義すると、

$$\begin{eqnarray} & & \sum_{k = r}^{l} a_{k}\times 10^{k-1} \equiv 0 \pmod P \\ & \Leftrightarrow & C_l - C_{r-1} \equiv 0 \pmod P \\ & \Leftrightarrow & C_l \equiv C_{r-1} \pmod P \end{eqnarray}$$

となる。つまり、部分文字列の左端$l$を固定したとき、問題の条件を満たすように部分文字列の右端を決めるには、上記の式を満たす累積和を持つインデックスを$l$の右側から見つければいい。問題の答えとして欲しいものは、条件を満たす部分文字列の個数であるから、(今回は配列でも問題ないが)mapで累積和の分布を記憶しつつ、$l$を文字列の右端から左端まで動かせば、それぞれの$l$に対して、$O(1)$で条件を満たす$r$の個数が数えられる。

類題

• ABC 105 D-Candy Distribution
• AGC 023 A-Zero-Sum Ranges