更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19638674

大意

三种牌分别有 $n , m, k$ 张，要求排列后满足相同的类型的牌不相邻的方案数。

$\newcommand{\binom}[2]{{#1 \choose #2}}$

思路

这集很考察基本功，组合好题。

考虑插板法，我们首先先把这个东西转换成上面的大意之后，我们先考虑把前两个人的位置考虑好，再考虑第三个人放的位置。

先安排核桃和小 $B$ 的位置，我们先枚举 $i$ 块 H，方案数是 $\binom{n - 1}{i - 1}$，现在我们要把 $m$ 个 B 也分成若干块，插入到这 $i$ 块 H 的空隙里。

为了使得 H 块之间分开，B 块的个数 $j$ 只有三种情况：

- $j = i - 1$

- $j = i$

- $j = i + 1$

其分别对应的情况为：B 块全在 H 块中间，方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i - 2}$，B 和 H 一头一尾（两种情况），方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i - 1} \times  2$，H 全在 B 中间，方案：$\binom{n - 1}{i - 1} \times \binom{m - 1}{i}$。然而此时的问题是，虽然 B 和 H 交错排列了，但是仍有一部分不合法的块内相邻的点，接下来我们需要做的就是将 R 插入到这个序列里面。

如果每一个 H 块内有 $x$ 个相邻的，那么就需要 $x - 1$ 个板来进行隔开，同样的对于 B 块内的也一样。所以说至少需要拿出来使得不合法变为合法的 R 需要 $(n - i) + (m - j)$ 个 R 来进行~~紧急避险~~，那么我们还能剩的 $k' = (k - n - m + i + j)$，那么我们剩下的这些 $k'$ 应该放到哪些地方呢？首先是 H 和 B 的中间是可以的，然后就是序列的开头和结尾是一定可以的，那么我们的剩余槽位是 $r = i + j$，若是 H 和 B 交错排列的话就是 $r = i + j + 1$，所以接下来的问题是把这剩下的 $k'$ 放到 $r$ 个剩余的槽位中（每个槽可以放 $0$ 个或多个），这个时候使用隔板法 $\binom{k' + r - 1}{r - 1}$，我们将其展开之后就是 $\binom{k - n - m + 2i + 2j}{i + j}$。

所以来说，对应的三种情况的总方案数就可以写出来了：

- $i = j - 1：\binom{k - n - m + 4i - 2}{2i - 1}$

- $i = j：\binom{k - n - m + 4i}{2i}$

- $i = j + 1：\binom{k - n - m + 4i + 2}{2i + 1}$

然后就没有了。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll mod = 998244353;
const ll N = 2e6 + 100;

ll n, m, k;
ll fac[N + 100], inv[N + 100];
ll ans;

ll mpow(ll aa,ll bb){
	ll res = 1;
	while(bb){
		if (bb&1) res = res * aa % mod;
		aa = aa * aa % mod;
		bb >>= 1;
	}
	return res;
}

ll C(ll aa,ll bb){
	if(aa < 0 || bb < 0 || aa > bb) return 0;
	return fac[bb] * inv[aa] % mod * inv[bb - aa] % mod;
}

int main(){
	freopen("UNO.in","r",stdin);
	freopen("UNO.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	fac[0] = 1;
	for(int i = 1;i <= N;i ++) fac[i] = (fac[i - 1] * i) % mod;
	for(int i = 0;i <= N;i ++) inv[i] = mpow(fac[i], mod - 2);
	for(int i = 1;i <= n;i ++){
		ans += C(i - 1, n - 1) * C(i - 2, m - 1) % mod * C(k - n - m + 2 * i - 1, 2 * i) % mod;
		ans += C(i - 1, n - 1) * C(i - 1, m - 1) % mod * C(k - n - m + 2 * i, 2 * i + 1) % mod * 2 % mod;
		ans += C(i - 1, n - 1) * C(i, m-1) % mod * C(k - n - m + 2 * i + 1, 2 * i + 2) % mod;
	}
	cout << (ans + mod) % mod<<'\n';
	return 0;
}