/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
0 以上 9 以下の整数からなる長さ N の数列 A=(A_1,\dots,A_N) があり、この順に左から右に並んでいます。
数列の長さが 1 になるまで、操作 F または操作 G を繰り返し行います。
- 操作 F ：左端の 2 つの値 ( x,y とする ) を削除した後、一番左に (x+y)\%10 を挿入する
- 操作 G ：左端の 2 つの値 ( x,y とする ) を削除した後、一番左に (x\times y)\%10 を挿入する
なお、a\%b は a を b で割った余りを意味します。
K=0,1,\dots,9 について、以下の問題に答えてください。
操作手順としてあり得るものは 2^{N-1} 通りありますが、このうち最終的に残る値が K となる操作手順は何通りありますか？
ただし答えは非常に大きくなる可能性があるので、998244353 で割った余りを求めてください。
制約
- 2 \leq N \leq 10^5
- 0 \leq A_i \leq 9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \dots A_N
出力
答えを 10 行に出力せよ。
ただし、i 行目には K=i-1 としたときの答えを出力せよ。
入力例 1
3 2 7 6
出力例 1
1 0 0 0 2 1 0 0 0 0
1 回目に操作 F 、2 回目に操作 F を行ったとき：数列は (2,7,6)→(9,6)→(5) となります。
1 回目に操作 F 、2 回目に操作 G を行ったとき：数列は (2,7,6)→(9,6)→(4) となります。
1 回目に操作 G 、2 回目に操作 F を行ったとき：数列は (2,7,6)→(4,6)→(0) となります。
1 回目に操作 G 、2 回目に操作 G を行ったとき：数列は (2,7,6)→(4,6)→(4) となります。
入力例 2
5 0 1 2 3 4
出力例 2
6 0 1 1 4 0 1 1 0 2
Score : 400 points
Problem Statement
We have a sequence of N integers between 0 and 9 (inclusive): A=(A_1, \dots, A_N), arranged from left to right in this order.
Until the length of the sequence becomes 1, we will repeatedly do the operation F or G below.
- Operation F: delete the leftmost two values (let us call them x and y) and then insert (x+y)\%10 to the left end.
- Operation G: delete the leftmost two values (let us call them x and y) and then insert (x\times y)\%10 to the left end.
Here, a\%b denotes the remainder when a is divided by b.
For each K=0,1,\dots,9, answer the following question.
Among the 2^{N-1} possible ways in which we do the operations, how many end up with K being the final value of the sequence?
Since the answer can be enormous, find it modulo 998244353.
Constraints
- 2 \leq N \leq 10^5
- 0 \leq A_i \leq 9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 \dots A_N
Output
Print ten lines.
The i-th line should contain the answer for the case K=i-1.
Sample Input 1
3 2 7 6
Sample Output 1
1 0 0 0 2 1 0 0 0 0
If we do Operation F first and Operation F second: the sequence becomes (2,7,6)→(9,6)→(5).
If we do Operation F first and Operation G second: the sequence becomes (2,7,6)→(9,6)→(4).
If we do Operation G first and Operation F second: the sequence becomes (2,7,6)→(4,6)→(0).
If we do Operation G first and Operation G second: the sequence becomes (2,7,6)→(4,6)→(4).
Sample Input 2
5 0 1 2 3 4
Sample Output 2
6 0 1 1 4 0 1 1 0 2