D - FG操作

得分：400

问题描述

给定一个由$N$个$0$到$9$之间（包括$0$和$9$）的整数组成的序列 $A=(A_1, \dots, A_N)$，按从左到右的顺序排列。

直到序列长度变为$1$为止，我们将重复执行以下操作$F$或$G$。

• 操作$F$：删除最左边的两个值（称为$x$和$y$），然后在最左边插入$(x+y)\%10$。
• 操作$G$：删除最左边的两个值（称为$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$

输出

输出应包含十行。
第 $i$ 行应该包含 $K=i-1$ 情况下的答案。

3
2 7 6

1
0
0
0
2
1
0
0
0
0

如果先执行操作$F$再执行操作$F$：序列变为$(2,7,6)→(9,6)→(5)$。
如果先执行操作$F$再执行操作$G$：序列变为$(2,7,6)→(9,6)→(4)$。
如果先执行操作$G$再执行操作$F$：序列变为$(2,7,6)→(4,6)→(0)$。
如果先执行操作$G$再执行操作$G$：序列变为$(2,7,6)→(4,6)→(4)$。

5
0 1 2 3 4

6
0
1
1
4
0
1
1
0
2