102203: [AtCoder]ABC220 D - FG operation

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:11 Solved:0

Description

Score : $400$ points

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

Input

题意翻译

给定一个数组 $A=(A_1,A_2 \dots A)$,从左到右排列,每个元素都是 $0\sim9$ 中的数字,你可以进行 $n-1$ 次操作使得数组长为 $1$,每次操作为以下两者之一: + 删除最左边两个数 $x,y$,在最左端插入 $(x+y) \bmod 10$。 + 删除最左边两个数 $x,y$,在最左端插入 $(x\times y)\bmod 10$。 对于 $k$ 从 $0$ 到 $9$,有多少种方式使得最后剩余的数是 $k$?对于每个 $k$ 输出一行答案,对 $998244353$ 取模。

Output

得分:400分

问题描述

我们有一个包含0到9(含)之间N个整数的序列:$A=(A_1, \dots, A_N)$,按从左到右的顺序排列。

我们反复执行以下操作$F$或$G$,直到序列长度变为1。

  • 操作$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$

输出

打印10行。
第$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

加入题单

上一题 下一题 算法标签: