CF1017H The Films

在《高堡奇人》的世界中，有 $m$ 种不同的电影结局。 Abendsen 拥有一个仓库和一个书架。起初，他的书架上有 $n$ 部有序的电影。在第 $i$ 个月，他会进行如下操作： 1. 清空仓库。 2. 向仓库中放入 $k_i \cdot m$ 部电影，每种结局各放 $k_i$ 部。 3. 他会思考这样一个问题：如果他将书架上的所有电影都放入仓库，然后从仓库中随机取出 $n$ 部电影并重新排列到书架上，那么书架上区间 $[l_i, r_i]$ 的结局序列是否不会改变的概率是多少？注意，他只是思考这个问题，书架实际不会发生变化。 请回答 Abendsen 的所有问题。 设该概率为分数 $P_i$。假设对于第 $i$ 个月，从仓库中取出 $n$ 部电影的总方案数为 $A_i$，则 $P_i \cdot A_i$ 总是整数。请输出每个月的 $P_i \cdot A_i \bmod{998244353}$。 $998244353$ 是一个质数，等于 $119 \cdot 2^{23} + 1$。 保证 $k$ 的不同取值不超过 $100$ 个。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \le n, m, q \le 10^5$，$n+q\leq 10^5$），分别表示初始书架上的电影数量、结局的种类数和月份数。 第二行包含 $n$ 个整数 $e_1, e_2, \ldots, e_n$（$1\leq e_i\leq m$），表示书架上第 $i$ 部电影的结局。 接下来的 $q$ 行，每行包含三个整数 $l_i$、$r_i$ 和 $k_i$（$1 \le l_i \le r_i \le n, 0 \le k_i \le 10^5$），表示第 $i$ 个询问。 保证 $k$ 的不同取值不超过 $100$ 个。

对于每个问题，输出一行答案。

在第一个样例的第二个询问中，向仓库中加入 $2 \cdot m$ 部电影后，仓库中的电影为：$\{1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4\}$。 共有 $26730$ 种方式选择电影，使得 $e_l, e_{l+1}, \ldots, e_r$ 的顺序不变，例如 $[1, 2, 3, 2, 2]$ 和 $[1, 2, 3, 4, 3]$ 都是这样的方式。 从仓库中取出 $n$ 部电影的总方案数为 $2162160$，所以你需要输出 $(\frac{26730}{2162160} \cdot 2162160) \bmod 998244353 = 26730$。 由 ChatGPT 4.1 翻译