CF1081C Colorful Bricks

tony102

2020 年 11 月 14 日

1667 次浏览

暂无评论

1135字数

题解

[Link](https://www.luogu.com.cn/problem/CF1081C)

## 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

```cpp
#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;
}
```

最后修改：2021 年 08 月 20 日