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}\)
然后就没有了。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long longconst 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;
}