【ABC】 164 D - Multiple of 2019

問題文

1から9までの数字のみからなる文字列Sが与えられます。
次のような条件を満たす整数の組$(i, j)(1\le i \le j \le |S|)$の総数を求めてください。
条件：$S$の$i$文字目から$j$文字目までを$10$進法の整数としてみると、この整数は$2019$の倍数である。

atcoder.jp

解説

$S$の長さを$n$、$S$の左から$k$番目の文字を$a_k$とする。
$(i, j)$が条件を満たすのは、

が$2019$の倍数の時である。
左から$k+1$文字以降の数字列を整数とみなした時の値を

と定義する。($T_n=0$) この$T_k$を用いると$A_{ij}$は

と表すことができる。
下の図を見ればよく分かるはず。

を効率的に計算するために次の性質を利用する。
$A _ {ij} = 10^ {n-j}(T _ {i-1} - T _ j)$を効率的に計算するために次の性質を利用する。

性質1

$2019$は$2$でも$5$でも割り切れないので$mod2019$では$10$に逆元が存在する。
$10n$が$2019$の倍数であることと$n$が2019の倍数であることは同値である。

ちなみに$2019=3*673$なので、$3n$が$2019$の倍数であることと$n$が$2019$の倍数であることは同値ではない。
$n=673$の場合、$3n=2019$となり$2019$の倍数であるが、$n=673$は$2019$の倍数にならない。

この性質より、$10^ {n-j}(T _ {i-1} - T _ j)$が2019の倍数であれば$T _ {i-1} - T _ j$も2019の倍数である。
$T _ {i-1} - T _ j$が2019の倍数のとき、

である。
$T _ i$を計算して$2019$で割った余りが同じものの個数を計算していく。
$2019$で割った余りを引数にもつ配列を準備する。
$DP[x] = m $は$2019$で割った余りが$x$である$T _ i$の個数が$ m $であることを意味する。
$ m $個の中から異なる$2$つを選んでくれば$A _ {ij}$が表現できるので、その総数は$ _ nC _ 2 = m ( m -1)/2$となる。

後はどのように$T _ i$を計算していくのかを考える。

当初の私の実装：

S = input()
mod = 2019
DP = [0] * mod
DP[0] = 1
t = 1
value = 0
for i in reversed(S):
    value += int(i) * t
    DP[value % mod] += 1
    t *= 10
print(int(sum([i * (i-1) / 2 for i in DP])))

これはDPではない。
DP[0] = 1にしているのは$T_n=0$のため。
例題にある$S=1817181712114$程度あれば$17$msで解けてしまうが$S$の桁数が増えると値が繰り上がるたびに巨大な数の$mod$を行う必要があり時間がかかる。

良い実装：

S = input()
mod = 2019
DP = [0] * mod
DP[0] = 1
t = 1
value = 0
for i in reversed(S):
    value += int(i) * t
    value %= mod
    DP[value] += 1
    t *= 10
    t %= mod
print(int(sum([i * (i-1) / 2 for i in DP])))

$T _ i = T _ {i+1} + 10^{n-i}a_i$を利用してDPを行う。
for文の最初では、value=$a_n$になる。
まずこれの$mod\;2019$を計算して得られた値を引数にとり配列DPの値を1だけ加算する。
$A=2019$として商$p_n$, 余りを$q_n$とすると、

となる。次のloopではvalue=$a_n + 10a_{n-1}$になる。
$10$を$2019$で割ったときの商と余りをそれぞれ$p^ {\prime} _ {10}, q^ {\prime} _ {10}$とすると、

となる。
上の第1項は$A$で割り切れることが確定しているので第2項を$A$で割り切れるかを調べれば良い。
つまり、第1項は保持する必要がなく、第2項のみを次に引き継ぐ。
t %= modで$10$の$mod$計算が行われて$q^ {\prime} _ {10}$が得られることになる。
これを次のloopで利用してvalue += int(i) * tで$q^ {\prime} _ {10}a_{n-1}$が$q_n$(value)に加算されている。

DPとmod計算ムズイ。