FG operation

题目描述

我们有一个长度为 $N$ 的整数序列，取值在 $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$ 取模给出结果。

输入格式

输入从标准输入给出，格式如下： $N$ $A_1$ $\dots$ $A_N$

输出格式

输出十行。
第 $i$ 行应包含当 $K=i-1$ 时的答案。

3
2 7 6

1
0
0
0
2
1
0
0
0
0

5
0 1 2 3 4

6
0
1
1
4
0
1
1
0
2

提示

$2 \leq N \leq 10^5$ $0 \leq A_i \leq 9$ 输入中的所有数值均为整数。如果我们第一次做操作 $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)$.

标签: AtCoder|abc220D

来源

AtCoder|abc220D