ABC164D
https://gyazo.com/badbc878097ba5f4df01c2d1902b3b13
考えたこと
iからjまでの範囲の余りが既知なら、10倍して一桁足して余りを取るのは定数時間
だけど各開始点についてのあまりを待つと全体で二乗のオーダー
追記、確かに定数ではあるが2019×200000だからTLEしそう
公式解説
少し違うアプローチ
範囲に対する演算を累積和と逆演算でやるのに似てる
それ自体は考察の時に少し考えたがダメだと勘違いした
https://gyazo.com/2bd8c05b48f05f4532c7434dc0a00e7b
$ x \equiv A_j - A_i \times 10^{j-i} \pmod{2019}
10の累乗部分が邪魔で使えない、と早合点
右から累積ではなく左から累積
数列ではなく数の桁なのでその方が自然
https://gyazo.com/1add8c37dc897eb81d632cfb85af2d94
$ x \times 10^{i-j} \equiv B_i - B_j \pmod{2019}
この問題ではxの余りが0かどうかにしか興味がない
10の累乗の掛け算は、10が2019と素だから無視できる