#P13370. [ABC225H] Social Distance 2

    ID: 12554 传统题 2000ms 888MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>CF2600组合数学多项式FFT分治生成函数

[ABC225H] Social Distance 2

AT_abc225_h [ABC225H] Social Distance 2

题目描述

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

有 MM 个人要坐在这些椅子上,坐法的得分由以下公式给出:

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

有 KK 个人(1≤i≤K1 \leq i \leq K)已经坐在了椅子 AiA_i 上。
剩下的 M−KM-K 个人的坐法共有 N−KPM−K{}_{N-K}\mathrm{P}_{M-K} 种。请你计算所有可能坐法的得分之和。

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

输入格式

输入通过标准输入给出,格式如下:

NN MM KK A1A_1 A2A_2 …\ldots AKA_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≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 2≤M≤N2 \leq M \leq N
  • 0≤K≤M0 \leq K \leq M
  • 1≤A1<A2<…<AK≤N1 \leq A_1 < A_2 < \ldots < A_K \leq N
  • 所有输入均为整数

样例解释 1

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

样例解释 2

所有坐法的得分都是 11。
坐法共有 5P5=120{}_5\mathrm{P}_5=120 种,所以答案为 120120。