AT_abc225_h [ABC225H] Social Distance 2

题目描述

有 $N$ 把椅子排成一列，分别编号为 $1, 2, \ldots, N$。
每把椅子最多只能坐一个人。

有 $M$ 个人要坐在这些椅子上，坐法的得分由以下公式给出：

设有人坐的椅子的编号按升序排列为 $B=(B_1,B_2,\ldots,B_M)$，
得分为 $\displaystyle\prod_{i=1}^{M-1} (B_{i+1} - B_i)$。

有 $K$ 个人（$1 \leq i \leq K$）已经坐在了椅子 $A_i$ 上。
剩下的 $M-K$ 个人的坐法共有 ${}_{N-K}\mathrm{P}_{M-K}$ 种。请你计算所有可能坐法的得分之和。

由于答案可能非常大，请输出答案对 $998244353$ 取模后的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $K$ $A_1$ $A_2$ $\ldots$ $A_K$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5 3 2
1 3

输出 #1

7

输入输出样例 #2

输入 #2

6 6 1
4

输出 #2

120

输入输出样例 #3

输入 #3

99 10 3
10 50 90

输出 #3

761621047

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq N$
• $0 \leq K \leq M$
• $1 \leq A_1 < A_2 < \ldots < A_K \leq N$
• 所有输入均为整数

样例解释 1

当第 3 个人坐在椅子 2 上时，得分为 $(2-1)\times(3-2)=1\times1=1$。
当第 3 个人坐在椅子 4 上时，得分为 $(3-1)\times(4-3)=2\times1=2$。
当第 3 个人坐在椅子 5 上时，得分为 $(3-1)\times(5-3)=2\times2=4$。
所以答案为 $1+2+4=7$。

样例解释 2

所有坐法的得分都是 $1$。
坐法共有 ${}_5\mathrm{P}_5=120$ 种，所以答案为 $120$。

由 ChatGPT 4.1 翻译