ABC242 C - 1111gal password

提出

code: python

n = int(input())

# 末尾に+=0,+-1の3種の数字を足してできていく

# 1と9は末尾に2種

# 1 2 3 4 5 6 7 8 9

# 11 12 21 22 23 ...

# 計算量オーバー

for i in range(1, 10):

dpi = True

解答

code: python

n = int(input())

MOD = 998244353

# dpij : 上から i 桁目まで決めて、i 桁目の数字が j である組み合わせ数（を 998244353 で割った余り)

# 0~10があることにする

# j=1,9 の場合はそれぞれ dpij−1、dpij+1 を省く必要があるが、この場合分けは面倒

# 初期値が0のままだから影響はない

dp = [0 * 11 for _ in range(n + 1)]

for i in range(1, 10):

dp1i = 1 # 上から1桁目の1～9はそれぞれ1通り

for i in range(1, n):

for j in range(1, 10):

dpi + 1j = (dpij - 1 + dpij + dpij + 1) % MOD

# print(dp)

# n = 2

# 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, [0, 2, 3, 3, 3, 3, 3, 3, 3, 2, 0

print(sum(dpn) % MOD)

テーマ

メモ