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