102203: [AtCoder]ABC220 D - FG operation
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
问题描述
我们有一个包含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