#P18918. [2026多校联测]序列询问

[2026多校联测]序列询问

序列询问

题目描述

给定长度为 NN 的序列 A=(A1,…,AN)A=(A_1,\ldots,A_N),每个元素均为 11 到 NN 之间的整数。

对于同样长度为 NN、元素范围为 [1,N][1,N] 的序列 BB,定义两个限制条件:

  1. 对于每个 i=1,…,Ni=1,\ldots,N,序列 BB 中数字 ii 的出现次数不超过 AiA_i。
  2. 对于每个 i=1,…,Ni=1,\ldots,N,序列 BB 中数字 BiB_i 的出现次数不超过 AiA_i。

给定 op∈{1,2}op\in\{1,2\}:当 op=1op=1 时,求只满足条件 2 的序列数;当 op=2op=2 时,求同时满足条件 1、2 的序列数。答案对 998244353998244353 取模。

输入格式

第一行两个整数 N,opN,op。第二行包含 NN 个整数 A1,…,ANA_1,\ldots,A_N。

输出格式

输出一个整数,表示答案对 998244353998244353 取模的结果。

样例 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,2)、(1,2,3)(1,2,3)、(1,3,2)(1,3,2)、(1,3,3)(1,3,3)、(2,1,3)(2,1,3)、(2,3,1)(2,3,1)、(2,3,3)(2,3,3)、(3,1,2)(3,1,2)、(3,2,1)(3,2,1)、(3,2,2)(3,2,2)。

数据范围

1≤N≤5001\le N\le500,1≤Ai≤N1\le A_i\le N,op∈{1,2}op\in\{1,2\},所有数均为整数。

子任务 N≤N\le opop 特殊性质 分值
1 55 2 无 9
2 1515 14
3 120120 1 10
4 500500 16
5 2 Ai≤2A_i\le2 11
6 5050 无 15
7 120120 12
8 500500 13

更多样例见附加文件 samples.zip。