ABC164 D - Multiple of 2019 - あっとのTECH LOG

問題原文

問題要旨

1 ~ 9 からなる文字列 $S$ が与えられる。
$S$ の連続する区間を10進数と見立てたとき、それが2019の倍数になっているようなものの通り数はいくつか。

$1 \leq |S| \leq 2 × 10^{5}$

解法

2019と10は互いに素なので、 $10^{n}X$ ga 2019の倍数ならば、 $10^{n + 1}X$ も $10^{n - 1}X$ も2019の倍数。
これを踏まえた上でsample1の 1817181712114 をみてみる。
18171 は 2019の倍数であるが、これは 1×10¹² + 8×10¹¹ + 1×10¹⁰ + 7×10⁹ + 1×10⁸ =1817100000000 = 2019 × 9 × 10⁸ という構造になっている。

つまり、 $10^{i}X_i + 10^{i - 1}X_{i-1} + ... + 10^{j}X_j$ が2019の倍数であればいい。これは累積和的に求められるので、ある $10^{i}X_i + 10^{i - 1}X_{i-1} + ... + 10^{j}X_j$ について2019で割ったあまりは高速に求められることになる。

ここからはZero-Sum-Rangesで、下からみて $(0, r)$ を2019で割った余りと $(0, l - 1)$ を2019で割った余りが同じならば、 $(l, r)$ を2019で割った余りが0になる。ので、累積的にみた2019で割った余りのそれぞれの出現数を辞書等でカウントすれば答えが求められる。

実装

from collections import Counter
S = input()[::-1]
MOD = 2019

X = [0]
for i, s in enumerate(S):
    X.append((X[-1] + int(s) * pow(10, i, MOD)) % MOD)

C = Counter(X)
ans = 0
for v in C.values():
    ans += v * (v - 1) // 2
print(ans)

感想

ZeroSumRages族、頭ではわかってるつもりだけどなかなか身につかない。。。
今の実力だと一目ではわからなくて、とりあえず累積をとってみるステップを丁寧に踏まないと見抜けない。。。ううむ記事を書いたけどぎこちないというかなんというか、式変形苦手なんだなぁと。。。
あとそれはそうなんですが、 0 が混じっちゃダメなのなるほどなぁという感じです。
精進します。