CF1081C Colorful Bricks

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()
{
    // freopen("code.in", "r", stdin);
    // freopen("code.out", "w", stdout);
    init();
    n = read(), m = read(), k = read();
    // for (int i = 1; i <= 10; ++ i) printf("%lld ", inv[i]);
    // puts("");
    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;
}