ABC335をPythonで（Fのみ）

AtCoder Beginner Contest 335（Sponsored by Mynavi）

F問題

基本は公式解説準拠
borderを$\sqrt{2\times 10^5} \fallingdotseq 500$より$500$に設定

F

n = int(input())
a = list(map(int, input().split()))
mod = 998244353

cnt = [1] + [0] * (n - 1)
border = 500
dp = [[0] * (border + 1) for _ in range(border + 1)]
ans = 0

for now in range(n):
    # a_iがborder以下だったものからの遷移を反映
    for to in range(1, border + 1):
        cnt[now] = (dp[to][now % to] + cnt[now]) % mod

    # a[now]がborder以下の場合、後から反映されるようにdpに記録
    if a[now] <= border:
        dp[a[now]][now % a[now]] = (cnt[now] + dp[a[now]][now % a[now]]) % mod

    # a[now]がborderを超えていた場合、即座に遷移させる
    else:
        for to in range(now + a[now], n, a[now]):
            cnt[to] = (cnt[now] + cnt[to]) % mod

    ans = (ans + cnt[now]) % mod

print(ans)