COGS 3349. [HSOI 2020] 是什么具体内容？

COGS 3349. [HSOI 2020] UNO 大意 三种牌分别有 \(n , m, k\) 张，要求排列后满足相同的类型的牌不相邻的方案数。 思路 这集很考察基本功，组合好题。 考虑插板法，我们首先先把这个东西转换成上面的大意之后，我们先考虑把前两个人的位置考虑好，再考虑第三个人放的位置。 先安排核桃和小 \(B\) 的位置，我们先枚举 \(i\) 块 H，方案数是 \(\dbinom{n - 1}{i - 1}\)，现在我们要把 \(m\) 个 B 也分成若干块，插入到这 \(i\) 块 H 的空隙里。 为了使得 H 块之间分开，B 块的个数 \(j\) 只有三种情况： \(j = i - 1\) \(j = i\) \(j = i + 1\) 其分别对应的情况为：B 块全在 H 块中间，方案：\(\dbinom{n - 1}{i - 1} \times \dbinom{m - 1}{i - 2}\)，B 和 H 一头一尾（两种情况），方案：\(\dbinom{n - 1}{i - 1} \times \dbinom{m - 1}{i - 1} \times 2\)，H 全在 B 中间，方案：\(\dbinom{n - 1}{i - 1} \times \dbinom{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\) 个或多个），这个时候使用隔板法 \(\dbinom{k' + r - 1}{r - 1}\)，我们将其展开之后就是 \(\dbinom{k - n - m + 2i + 2j}{i + j}\)。 所以来说，对应的三种情况的总方案数就可以写出来了： \(i = j - 1：\dbinom{k - n - m + 4i - 2}{2i - 1}\) \(i = j：\dbinom{k - n - m + 4i}{2i}\) \(i = j + 1：\dbinom{k - n - m + 4i + 2}{2i + 1}\) 然后就没有了。