ABC164D

D - Multiple of 2019

• 
• 考えたこと
  • iからjまでの範囲の余りが既知なら、10倍して一桁足して余りを取るのは定数時間
  • だけど各開始点についてのあまりを待つと全体で二乗のオーダー
  • だからここを定数の幅の頻度表にすれば良い
    • 追記、確かに定数ではあるが2019×200000だからTLEしそう
    • 計算量の見積もりミス
  • 未AC
• 公式解説
  • 少し違うアプローチ
  • 範囲に対する演算を累積和と逆演算でやるのに似てる
    • それ自体は考察の時に少し考えたがダメだと勘違いした
    • 
    • $x\equiv A_j-A_i\times 10^{j-i}(\mathrm{mod}2019)$
      • 10の累乗部分が邪魔で使えない、と早合点
    • 右から累積ではなく左から累積

      • 数列ではなく数の桁なのでその方が自然

      • 

      • $x\times 10^{i-j}\equiv B_i-B_j(\mathrm{mod}2019)$

      • この問題ではxの余りが0かどうかにしか興味がない

      • 10の累乗の掛け算は、10が2019と素だから無視できる

  • 左から累積→頻度→三角数