Link

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;
}