考察
駒はindexが厳密に増えるので、移動列と最終的な黒square集合は一対一に対応する。dp[i]をiへ到達する移動列数とすると、iからはj≡i mod A_iかつj>iの全squareへ加算する必要がある。
採用する候補: A_iをsqrt Nで大小分割し、小stepは剰余別累積、大stepは遷移先列挙する
棄却する候補: 全iからi+A_i,i+2A_i,…へdp[i]を直接配る
A_i=1が多数あると一頂点からO(N)遷移し、合計O(N^2)になる。
dp[1]=1としindexを昇順に処理する。iでは全d≤Bのbucket[d][i mod d]をdp[i]へ加える。A_i≤Bならdp[i]をbucket[A_i][i mod A_i]へ蓄え、A_i>Bならj=i+A_iからNまでstep A_iでdp[j]へ加える。最後に全dp[i]を合計する。
典型の発動条件
平方分割
発動条件: 更新step dが小さいと遷移先が多く、大きいと少ないという反比例構造がある。
d≤√Nを剰余bucket、d>√Nを陽な列挙に分ける。
剰余classへのlazy加算
発動条件: 遷移条件がj≡i mod dで、同じd,rから将来位置への寄与が共通する。
bucket[d][r]に到達数を保存し、位置jで該当する全小dの値を受け取る。
問題固有の要素
小stepから未来全体へ配る代わりに、未来位置が自分の剰余classを照会する向きへ主客転倒すると一更新O(1)になる。
別の問題へ持ち帰る視点: 等差数列更新はstepが小さい範囲をmod別の受取累積へ反転できる。
正当性
境界B≈√Nに対し、d≤Bはbucket[d][r]へdp[i]を足せば、以後同じ剰余rの位置が到着時にまとめて受け取れる。d>Bは一つのiからの遷移先が高々N/B個なので直接加算してよい。 小stepの多数遷移をlazyなbucketで共有し、大stepは遷移先が少ないため、両方の総量をO(N√N)へ均衡できる。
実装上の注意
- bucketへdp[i]を入れるのは、その時点までの全到達寄与をdp[i]へ集めた後に行う。停止は任意なので答えはdp[N]だけでなくΣdp[i]である。
復習の核
- 全A_i=1、全A_i>N/2、A_iが境界B前後、N=1を、全path列挙と比較しbucketの自己寄与が混ざらないことを確認する。
計算量と制約
時間
O(NB+N²/B)、B≈√NでO(N√N)。
空間
O(N+B²)、小stepの剰余bucket。
制約との対応
公式制約の確認範囲: Time limit: 2.5 sec; Memory limit: 1024 MiB; Constraints: All input values are integers.; 1 \le N \le 2 \times 10^5; 1 \le A_i \le 2 \times 10^5
出典