Existence Counting

AtCoder

IDarc174_e

Time4000ms

Memory256MB

Difficulty—

You are given integers $N$ and $K$. Consider a sequence $a=(a_1,a_2,\dots,a_K)$ of length $K$ that satisfies all of the following conditions: * $a_i$ is an integer such that $1 \le a_i \le N$. * All elements in $a$ are different. Let us arrange all possible sequences $a$ in lexicographical order to form a "sequence of sequences" called the dictionary $s$. Given a sequence $P$ that exists in the dictionary $s$, answer the following question for each integer $t=1,2,\dots,N$: * Find the number, modulo $998244353$, of sequences $b$ that satisfy all of the following conditions: * The sequence $b$ exists in the dictionary $s$. * The integer $t$ is contained in the sequence $b$. * The sequence $b$ is lexicographically less than or equal to the sequence $P$. What is lexicographical order for sequences? A sequence $A = (A_1, \ldots, A_{|A|})$ is **lexicographically strictly less** than $B = (B_1, \ldots, B_{|B|})$ if and only if 1. or 2. below is satisfied: 1. $|A|<|B|$ and $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$. 2. There is an integer $1\leq i\leq \min{|A|,|B|}$ that satisfies both of the following: * $(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})$ * $A_i < B_i$ ## Constraints * All input values are integers. * $1 \le K \le N \le 3 \times 10^5$ * $P$ satisfies the condition in the problem statement. ## Input The input is given from Standard Input in the following format: $N$ $K$ $P_1$ $P_2$ $\dots$ $P_K$ [samples]

Samples

Input #1

4 2
3 2

Output #1

5
5
4
2

In this input, $N=4,K=2$.  
Here, the dictionary $s$ is $((1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3))$.
Among the sequences in the dictionary $s$ that are lexicographically less than or equal to $(3,2)$,

*   five sequences contain $1$: $(1,2),(1,3),(1,4),(2,1),(3,1)$,
*   five sequences contain $2$: $(1,2),(2,1),(2,3),(2,4),(3,2)$,
*   four sequences contain $3$: $(1,3),(2,3),(3,1),(3,2)$,
*   two sequences contain $4$: $(1,4),(2,4)$.

Input #2

18 13
5 13 11 2 18 1 10 15 17 4 12 7 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Existence Counting",
    "description": {
      "content": "You are given integers $N$ and $K$. Consider a sequence $a=(a_1,a_2,\\dots,a_K)$ of length $K$ that satisfies all of the following conditions: *   $a_i$ is an integer such that $1 \\le a_i \\le N$. *   ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc174_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given integers $N$ and $K$. Consider a sequence $a=(a_1,a_2,\\dots,a_K)$ of length $K$ that satisfies all of the following conditions:\n\n*   $a_i$ is an integer such that $1 \\le a_i \\le N$.\n*   ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments