题面的简述：总共有$m$种书，书架上共有$n$本书，给出$n$本书的种类，并有$Q$个询问，每次询问给出$l, r, k$。每次询问时都会先出现$k * m$本书，每种书各$k$本，然后再加入书架上的$n$本书，共有$km + n$本书，从中随机取出$n$本随机顺序放回书架，问在$[l,r]$之间的书的种类和原来一样的概率，输出概率乘上总情况数，询问之间独立。
题面中已经把问题转化成有多少情况满足条件，我们考虑这个怎么算。首先考虑原位置不变的时候，我们考虑每一种颜色，用$c_{i}$表示$i$在$[l,r]$中出现次数，用$t_{i}$表示$i$在原序列中出现次数，如果只考虑$i$，那满足颜色$i$的方案数是：$C(t_{i} + k, c_{i})c_{i}!$，为了方便计算，我们直接用下降幂表示。那么根据乘法原理，所有的颜色都满足的方案数就是$\prod_{i = 1}^{m} (t_{i} + k)^{\underline{c_{i}}}$。剩下的对于除$[l,r]$之外的位置随便放书就可以了，所以对于每个询问的最后答案就是$ans = (mk + n - r + l - 1)^{ \underline{ n - r + l - 1 } } \prod_{i = 1}^{m} (t_{i} + k)^{\underline{c_{i}}}$。
我们考虑怎么计算上述式子，题中有一个很良心的性质，就是不同的$k$的个数不超过$100$，这提示我们可以对询问分类，对每一种$k$单独计算，接下来我们讲的都是对于某一个$k$计算询问的答案。
显然式子的前半部分我们可以$O(n)$预处理下降幂，询问时$O(1)$乘一下就行了，于是就是维护后半段，我们用莫队来实现，我们发现可以$O(1)$修改当前的值，因为某个位置颜色数的加一减一对答案的贡献是可以轻易知道的，那我们就可以完成这个问题了，只要松一下块大小就能过啦。
$\bigodot$技巧&套路：
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 200005, MOD = 998244353, BLO = 987; int n, m, Q, k, res; int fac[N], ifac[N], inv[N], prd[N]; int a[N], t[N], c[N], ans[N]; struct Que { int l, r, k, id; inline friend bool operator < (Que a, Que b) { if (a.k != b.k) return a.k < b.k; return (a.l / BLO != b.l / BLO)? (a.l < b.l) : (a.r < b.r); } } q[N]; int Down(int x, int y) { if (x < y) throw; return (LL) fac[x] * ifac[x - y] % MOD; } void Inc(int x) { if (!x) return; ++c[a[x]]; res = (LL) res * (t[a[x]] + k - c[a[x]] + 1) % MOD; } void Dec(int x) { if (!x) return; res = (LL) res * inv[t[a[x]] + k - c[a[x]] + 1] % MOD; --c[a[x]]; } void Solve(int ql, int qr) { int mk = (LL) k * m % MOD; prd[n] = 1; for (int i = n - 1; ~i; --i) { prd[i] = (LL) prd[i + 1] * (mk + n - i) % MOD; } res = 1; int l = 1, r = 0, L, R; for (int i = ql; i <= qr; ++i) { L = q[i].l; R = q[i].r; while (r < R) Inc(++r); while (l > L) Inc(--l); while (l < L) Dec(l++); while (r > R) Dec(r--); ans[q[i].id] = (LL) res * prd[r - l + 1] % MOD; } for (int i = l; i <= r; ++i) --c[a[i]]; } int main() { fac[0] = fac[1] = ifac[0] = ifac[1] = inv[1] = 1; for (int i = 2; i < N; ++i) { inv[i] = MOD - (LL) (MOD / i) * inv[MOD % i] % MOD; fac[i] = (LL) fac[i - 1] * i % MOD; ifac[i] = (LL) ifac[i - 1] * inv[i] % MOD; } scanf("%d%d%d", &n, &m, &Q); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); ++t[a[i]]; } for (int i = 1; i <= Q; ++i) { scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k); q[i].id = i; } sort(q + 1, q + 1 + Q); for (int i = 1, j; i <= Q; i = j + 1) { for (j = i; j < Q && q[j + 1].k == q[j].k; ++j); k = q[i].k; Solve(i, j); } for (int i = 1; i <= Q; ++i) { printf("%d\n", ans[i]); } return 0; }
原文：https://www.cnblogs.com/Dance-Of-Faith/p/9452060.html
