Score : $600$ points

问题描述

有 $N$ 把椅子排成一行，分别称为椅子1、椅子2、……、椅子$N$。 每把椅子只能坐一个人。

将会有 $M$ 个人坐在其中的 $M$ 把椅子上。这里我们定义得分如下：

$\displaystyle \prod_{i=1}^{M-1} (B_{i+1} - B_i)$，其中 $B=(B_1,B_2,\ldots,B_M)$ 是人们所坐椅子的索引经过排序后的列表。

已知第 $i$ 个人（$1 \leq i \leq K$）正坐在椅子 $A_i$ 上。
剩下的 $M-K$ 个人有 ${}_ {N-K} \mathrm{P} _ {M-K}$ 种方式就座。求所有这些方式下的得分之和。

由于这个和可能非常大，请计算它对 $998244353$ 取模的结果。

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

Problem Statement

There are $N$ chairs arranged in a row, called Chair $1$, Chair $2$, $\ldots$, Chair $N$.
A chair seats only one person.

$M$ people will sit on $M$ of these chairs. Here, let us define the score as follows:

$\displaystyle \prod_{i=1}^{M-1} (B_{i+1} - B_i)$, where $B=(B_1,B_2,\ldots,B_M)$ is the sorted list of the indices of the chairs the people sit on.

Person $i$ $(1 \leq i \leq K)$ is already sitting on Chair $A_i$.
There are ${} _ {N-K} \mathrm{P} _ {M-K}$ ways for the other $M-K$ people to take seats. Find the sum of the scores for all of these ways.

Since this sum may be enormous, compute it modulo $998244353$.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq N$
• $0 \leq K \leq M$
• $1 \leq A_1 \lt A_2 \lt \ldots \lt A_K \leq N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$ $K$

$A_1$ $A_2$ $\ldots$ $A_K$

Output

Print the answer.

Sample Input 1

5 3 2
1 3

Sample Output 1

7

If Person $3$ sits on Chair $2$, the score will be $(2-1) \times (3-2)=1 \times 1 = 1$.
If Person $3$ sits on Chair $4$, the score will be $(3-1) \times (4-3)=2 \times 1 = 2$.
If Person $3$ sits on Chair $5$, the score will be $(3-1) \times (5-3)=2 \times 2 = 4$.
The answer is $1+2+4=7$.

Sample Input 2

6 6 1
4

Sample Output 2

120

The score for every way of sitting will be $1$.
There are ${} _ {5} \mathrm{P} _ {5} = 120$ ways of sitting, so the answer is $120$.

Sample Input 3

99 10 3
10 50 90

Sample Output 3

761621047

update @ 2024/3/10 09:54:29