AtCoder Beginner Contest 179 振り返り

D - Leaping Tak

1からNまでの移動する通りの数を求める．

ただし，移動する際はK個の区間によって形成されたマスの数しか移動できない．

[1,2] [5,6,7] [9,10]など．

N は2*10**5以下．

MOD ＝998244353
 

解）

愚直に全部足すとO(N**2)の計算量．

Kの区間ごとに区間和を足すことで，O(KN)まで抑えられる．

解の数列とは別に累積和の数列を作っておくことにより，区間和を高速に求めることができる．

例）sum(A[3:8]) = S[7] - S[2]

初期値設定

dp = [0] * n

dp[0] = 1

acc_dp = [1] * n

それぞれの区間Kについて，足していく

        for d in lr:

            a = i - d[0]

            if a < 0:

                continue

            b = i - d[1] - 1

            val += acc_dp[a] - (acc_dp[b] if b >= 0 else 0)

（参考）

Submission #16904040 - AtCoder Beginner Contest 179

E - Sequence Sum

二乗してMODを取るのを繰り返す数列の要素和．

長さN，初期値X，MODがM．

解）取り得る値の種類はM通りしかないため，繰り返しが起きるまで計算することでO(M)で解ける．

ループ前＋ループ＋ループ後を足すことで答えになる．

そんなに難しくないはずなのに答えが合わなかったのは何故