分数: 400 点
问题陈述
我们有一系列 N 之间的整数 0 和 9 (含): A=(A_1, \dots, A_N),按此顺序从左到右排列。
直到序列的长度变成 1,我们会重复进行操作 F or 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.
样本输入 1
3 2 7 6
示例输出 1
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).
示例输入 2
5 0 1 2 3 4
示例输出 2
6 0 1 1 4 0 1 1 0 2