ABC164 D - Multiple of 2019 - ツバサの備忘録

解法

ここでは、 $S$ について下から $i$ 桁目の数字を $S_{i}$ と表記します。また、 $S$ の文字列の長さ、すなわち $|S|$ を $N$ とします。
加えて、 $X$ を $2019$ で割った余りを $X \ \%\ 2019$ と表記します。
まず、 $S$ について、桁ごとに分解して表現してみると、
$S_{1} \times 1 + S_{2} \times 10 + S_{3} \times 100 + ... S_{N} \times 10^{N-1}$
となります。
$S \% 2019$ は、次のように書くこともできます。
$(S_{1} \times 1 \ \% \ 2019+ S_{2} \times 10 \ \% \ 2019+ ... S_{N} \times 10^{N-1}\ \% \ 2019)\ \% \ 2019$
一般化すると、
$\displaystyle ( \sum_{i = 1}^{N} (S_{i} \times 10^{i-1} \ \% \ 2019) ) \ \% \ 2019$
ここで、 $Sum[k] = \displaystyle ( \sum_{i = 1}^{k} (S_{i} \times 10^{i-1} \ \% \ 2019) ) \ \% \ 2019$
と定義してあげると、
$Sum[0] = 0,Sum[k] = (Sum[k-1] + (S_{k} \times 10^{k-1}) \ \% \ 2019) \ \% \ 2019$
と
$10^{k} \ \% 2019 = (10^{k-1} \ \% \ 2019) \times 10 \ \% \ 2019$
の二つを組み合わせ、累積和のようにして $O(N)$ で計算することができます。
ここで、 $S$ の $i$ 桁目から $j$ 桁目までを取り出した数( $i \leqq j$ )は、これを $P$ として、
$\displaystyle P = \frac{\sum_{k = 1}^{j} (S_{k} \times 10^{k-1}) - \sum_{k = 1}^{i-1} (S_{k} \times 10^{k-1})}{10^{i-1}}$
$P$ が2019の倍数となるには、
$P \ \% \ 2019 = 0$
となっていればよいです。
2019と $10^{X}$ は互いに素なので、先ほどの数式のうち分子のみに着目することで、結局
$(\sum_{k = 1}^{j} (S_{k} \times 10^{k-1}) - \sum_{k = 1}^{i-1} (S_{k} \times 10^{k-1}) ) \ \% \ 2019 = 0$
であれば、 $P$ は2019の倍数ということがわかります。
これをさらに変形すると、
$(\sum_{k = 1}^{j} (S_{k} \times 10^{k-1} \ \% \ 2019)\ \% \ 2019 - \sum_{k = 1}^{i-1} (S_{k} \times 10^{k-1}\ \% \ 2019) \ \% \ 2019) = 0$
となり、結局
$\sum_{k = 1}^{j} (S_{k} \times 10^{k-1} \ \% \ 2019)\ \% \ 2019 = \sum_{k = 1}^{i-1} (S_{k} \times 10^{k-1}\ \% \ 2019) \ \% \ 2019$
という条件であるような $i,j$ のペアを探せばよいということがわかりました。
さて、この式は先ほど作成した $Sum[k]$ そのものの式で、
$Sum[i] = Sum[j]$
であるような $i,j$ のペアを探せばよいことになります。
$Cnt[k] = Sum[x] = k$ となるような $x$ の個数、という配列を用意しておき、

$Sum[i]$ を計算
$Cnt[Sum[i]]$ を答えに加算
$Cnt[Sum[i]]$ に1加算

という操作を、 $i = 0$ から繰り返して行けば、答えが求まります。 $Cnt$ については、取り得る添え字の値が $[0,2019)$ なので、そのサイズだけ確保しておけばよいです。

おまけ

今回のように、 $Sum$ と $Cnt$ を計算しながら答えを求めていく、というものはほかにもいくつかあります。
$Cnt$ は、今回添え字が最大で2019にしかならないのであらかじめ配列を確保しておくことができましたが、そうでない場合でも、列の長さが $N$ 以下のとき、種類も最大で $N$ 通りにしかならないことを利用すると、map等を駆使することで計算ができます。
$Sum$ も、単純な累積和でいいもの等があります。
ほかにも、 $2019$ が $10$ と互いに素でないケースが存在する問題等ありますので、是非見てみると良いと思います。
類題リスト↓