算法
(数学)
首先考虑只有 $0$ 对相邻块有相同颜色时的答案,如果从最左端开始染色,最左端可以染 $M$ 种颜色,其他块可以染 $M-1$ 种颜色,所以答案是 $M \times (M-1)^{N-1}$ 。如果至少有一对相邻块有相同颜色,可以考虑将哪几对相邻块粘在一起,这样就转化成了 $0$ 的情况。
所以,答案就是 $\sum\limits_{x=0}^K \binom{N-1}{x} \times M \times (M-1)^{N-1-x}$
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using mint = modint998244353;
// combination mod prime
struct combination {
vector<mint> fact, ifact;
combination(int n):fact(n+1),ifact(n+1) {
fact[0] = 1;
for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
ifact[n] = fact[n].inv();
for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n]*ifact[k]*ifact[n-k];
}
} c(200005);
int main() {
int n, m, k;
cin >> n >> m >> k;
mint ans;
mint col = m;
for (int x = n-1; x >= 0; --x) {
mint now = col;
now *= c(n-1, x);
if (x <= k) ans += now;
col *= m-1;
}
cout << ans.val() << '\n';
return 0;
}