Submission #49170411

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ABC335F Hop Sugoroku_平方分割
#入力受取  1-indexed
N = int(input())
A = [0] + list(map(int,input().split()))
MOD = 998244353
#DP[i]: コマの位置がiとなるときの、塗り方の場合の数
DP = [0] * (N+1)
DP[1] = 1
#平方分割(stepが小さい側)  G[x][y]: y mod xのマスに移動する場合の数の総和
sqrt_N = int(N**0.5)
G = [[0]*x for x in range(sqrt_N + 1)]
#遷移
for now in range(1, N+1):
    #stepが小さいものを受け取る
    for x in range(1, sqrt_N + 1):
        y = now % x
        DP[now] += G[x][y]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#ABC335F Hop Sugoroku_平方分割

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

#DP[i]: コマの位置がiとなるときの、塗り方の場合の数
DP = [0] * (N+1)
DP[1] = 1

#平方分割(stepが小さい側)  G[x][y]: y mod xのマスに移動する場合の数の総和
sqrt_N = int(N**0.5)
G = [[0]*x for x in range(sqrt_N + 1)]

#遷移
for now in range(1, N+1):
    #stepが小さいものを受け取る
    for x in range(1, sqrt_N + 1):
        y = now % x
        DP[now] += G[x][y]
    DP[now] %= MOD

    #A[now]の大小で場合分けして遷移
    if A[now] <= sqrt_N:  #小さい場合
        G[A[now]][now % A[now]] += DP[now]
        G[A[now]][now % A[now]] %= MOD
    else:  #大きい場合
        for next in range(now + A[now], N+1, A[now]):
            DP[next] += DP[now]

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

Submission Info

Judge Result