← 返回题目列表

AtCoder · abc220_d

G. FG 操作

中文机器翻译题面 查看原题

分数: 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