Score : $400$ points

问题描述

我们有一序列包含 $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$ 取模。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:43:33