Sol
这种跟旁边的的东西有限制的题目通常可以用插板法做
相当于现在我要插$k$块板子进去,现在这一排砖被分成了$k+1$段
现在钦定有第一块板子右边那块砖的颜色,有 $m$ 种选择。那么剩下的 $k-1$ 块板子右边的都可以涂 $m-1$ 种颜色,就有$(m-1)^k$ 种方案。同时保证板子左边和右边的颜色不同。
现在的问题是,要在这$n$块砖中选择一些位置插板子,因为 $n$ 个球只有 $n-1$ 个位置,所以有 $\binom{n-1}{k}$ 种方案。
根据乘法原理可得最后的答案是:
$$\binom{n-1}{k}\times m(m-1)^k$$
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SIZE = 2e3 + 5;
const int mod = 998244353;
int n, m, k;
int fac[SIZE], inv[SIZE];
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ae86::read;
inline int qPow(int a, int b)
{
int ans = 1;
while (b) {
if (b & 1) ans = ans * a % mod;
b >>= 1, a = a * a % mod;
}
return ans % mod;
}
inline void init()
{
fac[0] = 1;
for (int i = 1; i <= 2000; ++ i) fac[i] = fac[i - 1] * i % mod;
inv[2000] = qPow(fac[2000], mod - 2) % mod;
for (int i = 1999; i >= 0; -- i) inv[i] = inv[i + 1] * (i + 1) % mod;
}
inline int C(int x, int y)
{
if (y == 0) return 1;
return ((fac[x] % mod) * (inv[y] * inv[x - y] % mod) % mod);
}
signed main()
{
init();
n = read(), m = read(), k = read();
if (!k) {
int ans = m * qPow(m - 1, k) % mod;
printf("%lld\n", ans % mod);
}
else {
int ans = C(n - 1, k) * m % mod * qPow(m - 1, k) % mod;
printf("%lld\n", ans);
}
return 0;
}