P13349 「ZYZ 2025」自然数序列

给定长度为 $n$ 的**正整数**序列 $a$，有 $q$ 次询问。对于每次询问，给出 $l,r,k$ 和 $k$ 个限制条件，求有多少个长度为 $n$ 的**自然数**序列 $b$ 满足 $l\le\sum\limits_{i=1}^na_ib_i\le r$ 且满足这 $k$ 个限制条件，对 $998244353$ 取模。 对于每个限制条件，给出 $x,y$，要求 $b_x=y$。 我们称两个长度为 $n$ 的序列 $b,b'$ 是不同的，当且仅当存在不超过 $n$ 的正整数 $i$ 满足 $b_i\not=b_i'$。

输入的第一行包含两个正整数 $n,q$。 第二行包含 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。 接下来有 $q$ 次询问，对于每一次询问： 第一行包含三个非负整数 $l,r,k$。 接下来 $k$ 行，每行两个非负整数 $x,y$，代表一条限制条件。

对于每一次询问，输出一行一个整数，表示对应的答案。

**【样例解释】** 对于第一次询问，有以下 $4$ 个序列 $b$ 符合条件：$\{0,0,0,2\},\{0,1,0,0\},\{5,0,0,1\},\{10,0,0,0\}$。 序列 $\{3,0,1,1\}$ 不符合条件，因为不满足限制 $b_3=0$；序列 $\{1,1,1,1\}$ 不符合条件，因为不满足 $\sum\limits_{i=1}^na_ib_i=10$。 **【数据范围】** **本题采用捆绑测试。** |子任务编号|特殊性质|分值| |:-:|:-:|:-:| |$0$|$n,l,r,q\le8$|$10$| |$1$|$n,l,r,q\le100$|$15$| |$2$|$k=1$ 且 $l=r$|$25$| |$3$|$l=r$|$25$| |$4$|无|$25$| 对于所有的测试数据，保证：$0\le l,r,y\le5\times10^3$，$1\le n,a_i\le 5\times10^3$，$1\le q\le 5\times 10^4$，$0\le k\le8$，$1\le x\le n$。对于一次询问，保证每一条限制的 $x$ 互不相同。