提出 #49129100

---

ソースコード 拡げる

#ABC335F

#入力受取  1-indexed
N = int(input())
A = [0] + list(map(int,input().split()))
MOD = 998244353

#DP[i]: コマがiまで来たときの、iまでの塗り方の場合の数
DP = [0] * (N+1)
DP[1] = 1

#sub[i]: (一度に移動する幅step, 組み合わせ数comb)
#        幅stepの倍数の移動を行い、ちょうどマスiに止まる組み合わせ数comb
sub = [[] for _ in range(N+1)]

#same[i]: マスiにA[i]のstepで入るものがあればTrue
same = [False] * (N+1)

for now in range(1,N+1):
    #DP[now]は遷移時に計算済み。MODで割っておく
    DP[now] %= MOD

    #step == A[i]が存在しない場合、とりあえず(A[i], 0)を足す
    if same[now] == False:
        sub[now].append((A[now],0))

    #順に遷移
    while sub[now]:
        step, comb = sub[now].pop()
        next = now + step
        if next > N:
            continue

        #step == A[now]の場合、累積和の要領でcombを増やす
        if step == A[now]:
            comb += DP[now]
            comb %= MOD

        #nextに遷移  ここでDP[next]に加算処理を行う
        sub[next].append((step,comb))
        DP[next] += comb
        if A[next] == step:
            same[next] = True


#答えを出力
print(sum(DP) % MOD)

提出情報

ジャッジ結果