老题解批量补档。
http://222.180.160.110:61235/contest/3887/problem/3
有 \(N\) 个格子排成一排，你需要用至多 \(M\) 种颜色给这些格子染色，每个格子恰好染成某一种颜色，不需要每种颜色都用上。求有多少种染色方案满足相邻的同色格子不超过 \(K\) 对。
不妨将一对相邻同色格子称为同色对，将一串连续的相同颜色称作一段，那么最极端的情况下会有 \(N\) 段（即不存在同色对）。
构造一段长度为 \(L\) 的 \(L\) 段序列（即不存在同色对）。此时将任意一段长度增加 1，则出现一对同色对。接下来，不论是选取长度为 2 的那一段，还是选取剩下的长度为 1 的段，将其长度增加 1，都会且仅会增加 1 对同色对。
以此类推，进行 \(K\) 次「选取一段并将其长度增加 1」的操作，可得到刚好 \(K\) 个同色对，此时序列长度为 \(L + K\)，而 段数没有变化，仍是一开始的 \(L\)。 所以反过来，如果在长度为 \(N\) 的序列中存在 \(K\) 个同色对，那么段数为 \(N-K\)。很难想象题解用「所以」两个字直接略过了上述推导过程
由此，我们只要考虑分别将序列任意分为非空的 \(N-K\sim N\) 段，就可以解决问题，隔板法可得将 \(N\) 分为 \(T\) 段的方案数为 \(C_{N-1}^{T-1}\)。在此基础上考虑染色，由乘法原理，将 \(T\) 段染色的方案为 \((m - 1)^{T - 1}\times M\)。
取 \(T=N-K\sim N\) 并求和问题即解决。
namespace XSC062 {
using namespace fastIO;
const int maxn = 2e5 + 15;
const int mod = 998244353;
int fac[maxn];
int n, m, k, res;
inline int qkp(int x, int y) {
int res = 1;
while (y) {
if (y & 1)
(res *= x) %= mod;
(x *= x) %= mod;
y >>= 1;
}
return res;
}
inline int inv(int x) {
return qkp(x, mod - 2);
}
inline int A(int n, int m) {
return (fac[n] * inv(fac[n - m])) % mod;
}
inline int C(int n, int m) {
return (A(n, m) * inv(A(m, m))) % mod;
}
int main() {
read(n), read(m), read(k);
fac[0] = 1;
for (int i = 1; i <= n + 5; ++i)
fac[i] = (fac[i - 1] * i) % mod;
for (int i = n - k; i <= n; ++i) {
(res += ((C(n - 1, i - 1) *
qkp(m - 1, i - 1)) % mod
* m) % mod) %= mod;
}
print(res, '\n');
return 0;
}
} // namespace XSC062
#undef int