组合计数神题。下文的 \(m\) 指原题面中的 \(d\)，\(k\) 指原题面中的 \(r\)。
考虑最后每个人得到的宝石数量的序列 \(s_1, s_2, \ldots, s_n\)，考虑这种方案的出现次数。首先要在 \(m\) 次操作中分别选 \(s_i - 1\) 次给第 \(i\) 个人，方案数为 \(\frac{m!}{\prod\limits_{i = 1}^n (s_i - 1)!}\)；然后对于一个人，当它的宝石数为 \(k\) 时，选择一颗变成两颗的方案数为 \(k\)，所以每个人还有 \((s_i - 1)!\) 种方案的贡献，乘起来发现 \((s_i - 1)!\) 被约掉了，也就是说对于任意一种 \(s_1, s_2, \ldots, s_n\)，它们出现概率均等。
于是题目变成了，一个序列的价值为前 \(k\) 大元素之和，求所有满足 \(\sum\limits_{i = 1}^n s_i = m\) 的序列 \(s\) 的价值之和（最后要除个方案数 \(\binom{n + m - 1}{n - 1}\) 和加上原有的 \(k\) 个）。
考虑对于一个固定的序列 \(s\)，我们以这样的方式计算它的价值：\(\sum\limits_{a > 0} \min(k, \sum\limits_{i = 1}^n [s_i \ge a])\)。可以想象成一个柱状图，就是把原来的从左到右算面积变成从上到下算面积。这样可以方便许多。
那么设 \(f_{a, i}\) 为对于一个序列 \(s\)，恰好有 \(i\) 个元素的值 \(\ge a\) 的这样的序列个数；考虑二项式反演，设 \(g_{a, i}\) 为对于一个序列 \(s\)，钦定有 \(i\) 个元素的值 \(\ge a\) 的这样的序列个数。\(g_{a, i}\) 是好求的，相当于选 \(i\) 个位置让他们 \(\ge a\)，就变成了一个和为 \(m - ai\) 的插板，那么：
且：
反演得：
答案即为：
这样已经可以做 \(O(n^2m)\) 了，但是还不够。考虑把 \(f\) 扔掉，直接计算每个 \(g_{a, i}\) 对答案的贡献，那么答案也可以表示成：
后面那一坨求和式子看上去不能考虑组合意义，那么可以尝试递推。设 \(v_{n, k} = \sum\limits_{i = 1}^n (-1)^{n - i} \binom{n}{i} \min(i, k)\)，那么根据 \(\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}\) 可以裂项后尝试递推：
那么我们得到了 \(v_{n, k} = -v_{n - 1, k} + v_{n - 1, k - 1}\)，边界 \(\forall k > 0, v_{1, k} = 1\)。考虑组合意义，可以看作是，\(n - 1\) 次选 \(i\) 次让 \(k - 1\)，\(n - 1 - i\) 次让 \(k\) 不 \(-1\) 并变号，那么有 \(v_{n, k} = \sum\limits_{i = 0}^{k - 1} (-1)^{n - 1 - i} \binom{n - 1}{i}\)。再尝试递推：
最后一步是运用了正负项抵消。那么我们有 \(\forall k > 0, v_{1, k} = 1, \forall n > 1, v_{n, k} = (-1)^{n - k} \binom{n - 2}{k - 1}\)。
再来考虑答案的式子：
分别代入 \(g_{a, i}, v_{i, k}\) 的式子得：
关注后半部分：
注意到 \(ai \le m\)，所以暴力算的复杂度就是 \(O(m \log m)\) 的。但是还能更优。
其中 \(h_i = \sum\limits_{i \mid t} \binom{m + n - t - 1}{n - 1}\)，可以高维前缀和预处理出。
至此，我们终于以 \(O(n + m \log \log m)\) 的复杂度完成了这题。
code
// Problem: #3405. 「2020-2021 集训队作业」Gem Island 2
// Contest: LibreOJ
// URL: https://loj.ac/p/3405
// Memory Limit: 512 MB
// Time Limit: 1200 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 30000100;
const ll mod = 998244353;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
int n, m, K, N, fac[maxn], ifac[maxn], f[maxn], pr[maxn / 10], tot;
bool vis[maxn];
inline ll C(int n, int m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return 1LL * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%d%d%d", &n, &m, &K);
N = n + m;
fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = 1LL * fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = 1LL * ifac[i + 1] * (i + 1) % mod;
}
for (int i = 2; i <= m; ++i) {
if (!vis[i]) {
pr[++tot] = i;
}
for (int j = 1; j <= tot && i * pr[j] <= m; ++j) {
vis[i * pr[j]] = 1;
if (i % pr[j] == 0) {
break;
}
}
}
for (int i = 1; i <= m; ++i) {
f[i] = C(n + m - i - 1, n - 1);
}
for (int i = 1; i <= tot; ++i) {
for (int j = m / pr[i], k = m / pr[i] * pr[i]; j; --j, k -= pr[i]) {
int &t = f[j];
t = (((t += f[k]) >= mod) ? t - mod : t);
}
}
ll ans = 1LL * n * f[1] % mod;
for (int i = 2; i <= n; ++i) {
ans = (ans + C(n, i) * (((i - K) & 1) ? mod - 1 : 1) % mod * C(i - 2, K - 1) % mod * f[i]) % mod;
}
ans = ans * qpow(C(n + m - 1, n - 1), mod - 2) % mod;
ans = (ans + K) % mod;
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}