Da 1y3。
今天因为初赛实在是没时间（懒得）写题了www，就放一道之前模拟赛场切的题吧。还有这个 CF 评分是假的，难点在于看懂题。
考虑令 \(c_i\) 表示序列中 \(i\) 元素的出现次数，对于一次询问 \(l,r\)，令 \(d_i\) 表示 \(a_l,a_{l+1},\cdots,a_r\) 中 \(i\) 元素的出现次数。令 \(A_n^m=\frac{n!}{(n-m)!}=n^{\underline{m}}\) 为从 \(n\) 个数中选出 \(m\) 个组成排列的方案数，那么 \([l,r]\) 询问的答案为：
\[\left(\prod\limits_{i=1}^mA_{k+c_i}^{d_i}\right)A_{n+mk-(r-l+1)}^{n-(r-l+1)} \]我们发现对于相同的 \(k\)，排列数底下的数是相同的，并且括号右边乘上的排列数显然只和 \(r-l+1\) 及询问区间长度有关。
注意到 \(k\) 不超过 \(100\) 种，这启示我们将询问按照 \(k\) 分类。对于 \(k\) 一定的询问，右边的部分可以 \(O(n)\) 预处理出来。并且对于任意的 \(i\in [1,m]\)，\(d_i\gets d_i+1\) 或者 \(d_i\gets d_{i}-1\) 时，括号内的答案是好计算的。所以可以直接跑莫队，取两部分求乘积即可。
我们分析一下复杂度，设 \(t\) 为 \(k\) 的个数，\(q_i(1\le i\le t)\) 表示第 \(i\) 种 \(k\) 的询问的个数，则 \(\sum\limits_{i=1}^tq_i=q\)。对于第 \(i\) 个 \(k\) 的询问我们取块长 \(\frac{n}{\sqrt{q_i}}\) ，这部分的复杂度为 \(O(n\sqrt{q_i})\)，则我们关心 \(\sum\limits_{i=1}^t\sqrt{q_i}\) 的最大值，而根据卡尔松不等式：
\[\begin{matrix}\underbrace{(1+1+\cdots +1)}\\t\end{matrix}\left(\sum\limits_{i=1}^tq_i\right)\ge \left(\sum\limits_{i=1}^t\sqrt{q_i}\right)^2 \]则 \(\sum\limits_{i=1}^t \sqrt{q_i}\le \sqrt{t\left(\sum\limits_{i=1}^tq_i\right)}=\sqrt{tq}\)，所以复杂度是 \(O(n\sqrt{tq})\) 的，但是常数不大所以直接冲过去了。
#include <bits/stdc++.h>
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
#if ONLINE_JUDGE
#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
#else
#define gh() getchar()
#endif
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define ins insert
#define era erase
typedef tuple<int, int, int> tu3;
typedef pair<int, int> pi;
inline int rd() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void wr(int x) {
if (x < 0) x = ~(x - 1), putchar('-');
if (x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
}
using namespace vbzIO;
const int N = 3e5 + 100;
const int P = 998244353;
int n, m, q, len, t1, sum;
int t2[N], a[N], c[N], ct[N], ans[N], inv[N];
struct qry {
int l, r, id;
qry () { }
qry (int _l, int _r, int _id) : l(_l), r(_r), id(_id) { }
bool operator < (const qry &rhs) const {
return l / len == rhs.l / len ? (((l / len) & 1) ? (r < rhs.r) : (r > rhs.r)) : l < rhs.l;
}
};
vector<qry> qr[N];
int qpow(int p, int q) {
int res = 1;
for (; q; q >>= 1, p = 1ll * p * p % P)
if (q & 1) res = 1ll * res * p % P;
return res;
}
void init(int lim) {
inv[0] = inv[1] = 1;
for (int i = 2; i <= lim; i++)
inv[i] = 1ll * inv[P % i] * (P - P / i) % P;
}
void add(int id) { t1 = 1ll * t1 * (c[a[id]] - ct[a[id]]) % P, ct[a[id]]++; }
void del(int id) { ct[a[id]]--, t1 = 1ll * t1 * inv[c[a[id]] - ct[a[id]]] % P; }
int main() {
n = rd(), m = rd(), q = rd(), init(3e5);
for (int i = 1; i <= n; i++) a[i] = rd();
for (int i = 1, l, r, k; i <= q; i++) {
l = rd(), r = rd(), k = rd();
qr[k].pb(qry(l, r, i));
}
for (int i = 0; i <= 2e5; i++) {
if (!qr[i].size()) continue;
memset(c, 0, sizeof(int) * (m + 10)), sum = 0;
for (int j = 1; j <= n; j++) c[a[j]]++;
for (int j = 1; j <= m; j++) c[j] += i, ct[j] = 0;
t2[n] = 1, sum = (n + 1ll * m * i % P) % P;
for (int j = n - 1, k = (sum - j + P) % P; j; j--, k = (k + 1) % P)
t2[j] = 1ll * t2[j + 1] * k % P;
len = ceil(n / sqrt(qr[i].size()));
sort(qr[i].begin(), qr[i].end());
int l = t1 = 1, r = 0;
for (qry j : qr[i]) {
while (l > j.l) add(--l);
while (r < j.r) add(++r);
while (l < j.l) del(l++);
while (r > j.r) del(r--);
ans[j.id] = 1ll * t1 * t2[r - l + 1] % P;
}
}
for (int i = 1; i <= q; i++)
wr(ans[i]), pc('\n');
return 0;
}