FG operation

AtCoder

IDabc220_d

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

3
2 7 6

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)$.

Input #2

5
0 1 2 3 4

Output #2

API Response (JSON)

{
  "problem": {
    "name": "FG operation",
    "description": {
      "content": "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 d",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc220_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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.\nUntil the length of the sequence becomes $1$, we will repeatedly d...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments