ABC164D
考えたこと
iからjまでの範囲の余りが既知なら、10倍して一桁足して余りを取るのは定数時間
だけど各開始点についてのあまりを待つと全体で二乗のオーダー
だからここを定数の幅の頻度表にすれば良い
追記、確かに定数ではあるが2019×200000だからTLEしそう
計算量の見積もりミス
公式解説
少し違うアプローチ
範囲に対する演算を累積和と逆演算でやるのに似てる
それ自体は考察の時に少し考えたがダメだと勘違いした
x \equiv A_j - A_i \times 10^{j-i} \pmod{2019}
10の累乗部分が邪魔で使えない、と早合点
右から累積ではなく左から累積
数列ではなく数の桁なのでその方が自然
x \times 10^{i-j} \equiv B_i - B_j \pmod{2019}
この問題ではxの余りが0かどうかにしか興味がない
10の累乗の掛け算は、10が2019と素だから無視できる
左から累積→頻度→三角数
Related Pages
- →帰着する力×計算量の見積もり×ABC165C×AGC048×思考の部品×abc034c×arc106d×貪欲法の証明パターン×abc146d×agc038a×agc036a×ARC083A×arc026b×arc040c×arc024b×cf17_final_c×agc024b×soundhound2018_summer_qual_c×panasonic2020_d×arc091b×公式より小オーダー×abc147d×abc006c×abc070d×abc125c×agc014b×agc018a×abc132d×ABC014C×aising2019C×code_festival_2017_quala_c×abc109d×abc112c×agc003b×arc062b×agc024c×indeednow_2015_quala_c×abc016d×abc121d×agc033a×arc054b×arc092a×arc052b×abc080c×tenka1_2017c×abc105c×abc032c×ABC054C×diverta2019_2_c×indeednow_2015_qualc_c×abc089d×abc157d×abc012d×abc154e×arc032b×abc126d×arc081b×abc138e×tenka1_2018_c×nikkei2019_qual_c×abc019c×abc140d×arc042b×arc064a×arc034b×abc124d×arc037b×arc097b×arc097a×arc036b×abc096d×abc150d×doing×sumitb2019_e×nomura2020c×code_festival_qualb_c×m_solutions2019d×AGC019B×abc103d×agc029b×arc087b×arc014c×abc165e×agc006b×codefestival_2016_final_c×agc031b×agc022b×agc032b→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]