序列询问
题目描述
给定长度为 N 的序列 A=(A1,…,AN),每个元素均为 1 到 N 之间的整数。
对于同样长度为 N、元素范围为 [1,N] 的序列 B,定义两个限制条件:
- 对于每个 i=1,…,N,序列 B 中数字 i 的出现次数不超过 Ai。
- 对于每个 i=1,…,N,序列 B 中数字 Bi 的出现次数不超过 Ai。
给定 op∈{1,2}:当 op=1 时,求只满足条件 2 的序列数;当 op=2 时,求同时满足条件 1、2 的序列数。答案对 998244353 取模。
输入格式
第一行两个整数 N,op。第二行包含 N 个整数 A1,…,AN。
输出格式
输出一个整数,表示答案对 998244353 取模的结果。
样例 1
输入
3 2
1 2 3
输出
10
样例 2
输入
3 1
2 1 3
输出
12
样例 3
输入
14 2
6 5 14 3 6 7 3 11 11 2 3 7 8 10
输出
628377683
样例 4
输入
14 1
6 5 14 3 6 7 3 11 11 2 3 7 8 10
输出
858473574
样例 1 解释
符合要求的十个序列为:(1,2,2)、(1,2,3)、(1,3,2)、(1,3,3)、(2,1,3)、(2,3,1)、(2,3,3)、(3,1,2)、(3,2,1)、(3,2,2)。
数据范围
1≤N≤500,1≤Ai≤N,op∈{1,2},所有数均为整数。
| 子任务 |
N≤ |
op |
特殊性质 |
分值 |
| 1 |
5 |
2 |
无 |
9 |
| 2 |
15 |
14 |
| 3 |
120 |
1 |
10 |
| 4 |
500 |
16 |
| 5 |
2 |
Ai≤2 |
11 |
| 6 |
50 |
无 |
15 |
| 7 |
120 |
12 |
| 8 |
500 |
13 |
更多样例见附加文件 samples.zip。