COGS 3349. [HSOI 2020] 是什么具体内容？
摘要：COGS 3349. [HSOI 2020] UNO 大意 三种牌分别有 (n , m, k) 张，要求排列后满足相同的类型的牌不相邻的方案数。 思路 这集很考察基本功，组合好题。 考虑插板法，我们首先先把这个东西转换成上面的大意之后，
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 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;
}