AtCoder-ABC220 D - FG operation【Python解答例】 - ebisukeプログラミング初心者脱出黙示録

AtCoder Beginner Contest220 D - FG operation

問題文

0 以上 9 以下の整数からなる長さ N の数列 A=(A 1 ,…,A N ) があり、この順に左から右に並んでいます。

数列の長さが 1 になるまで、操作 F または操作 G を繰り返し行います。

操作 F ：左端の 2 つの値 ( x,y とする ) を削除した後、一番左に (x+y)%10 を挿入する
操作 G ：左端の 2 つの値 ( x,y とする ) を削除した後、一番左に (x×y)%10 を挿入する
なお、a%b は a を b で割った余りを意味します。

K=0,1,…,9 について、以下の問題に答えてください。

操作手順としてあり得るものは 2 N−1 通りありますが、このうち最終的に残る値が K となる操作手順は何通りありますか？
ただし答えは非常に大きくなる可能性があるので、998244353 で割った余りを求めてください。

制約

・2≤N≤10 ^5
・0≤A i ≤9
・入力は全て整数

解答例

mod = 998244353

n = int(input())

A = list(map(int, input().split()))

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

dp[0][A[0]] = 1
for i in range(n-1):
    y = A[i+1]
    for j in range(10):
        if dp[i][j] != 0:
            x = j
            xf = (x+y) % 10
            xg = (x*y) % 10

            dp[i+1][xf] = (dp[i+1][xf] + dp[i][x]) % mod
            dp[i+1][xg] = (dp[i+1][xg] + dp[i][x]) % mod

for i in range(10):
    print(dp[n-1][i])