题解 P6561 【[SBCOI2020] 人】
duyi
·
·
题解
来呀，快活呀↓
超超超超超爽的阅读体验
题目大意
给定三个正整数m, a, b。要求在[1,2m]中选出a个奇数，b个偶数，并且选出的数两两不相邻。问有多少种选择的方案。方案数对998244353取模。
数据范围：$1\leq a,b\leq m\leq 10^6$。$a+b\leq m$。$1\leq T\leq 10^6$。
## 本题题解
考虑相邻的一奇一偶，也就是形式化地表述为$2i+1$, $2i+2$ ($0\leq i<m$)这两个数，它们不可能同时被选中。对于第$i$组数，如果$2i+1$（奇数）被选中，称这一组为$\text{A}$；如果$2i+2$（偶数）被选中，称这一组为$\text{B}$；如果都没有被选中，称这一组为$\text{C}$。则任何一种合法的选择方案，可以被表示为一个长度为$m$的$\text{ABC}$串，其中有$a$个$\text{A}$，$b$个$\text{B}$，和$m-a-b$个$\text{C}$，并且不允许出现$\text{BA}$这个子串。我们相当于要求这样的$\text{ABC}$串的数量。
先不考虑$\text{A}$。$\text{B}$和$\text{C}$的相对位置关系可以任意安排，它们共有$b+(m-a-b)=m-a$个，所以任意安排的方案数是${m-a\choose b}$。
再插入$\text{A}$。$\text{A}$不能被插入在$\text{B}$后面，除此之外其他任何位置都是可以的。考虑第$1$个$\text{A}$，它可以被插入在最前面，或者某个$\text{C}$后面，所以有$m-a-b+1$种方案；第$2$个$\text{A}$，除了最前面和某个$\text{C}$后面以外，还能插入在第$1$个$\text{A}$后面，所以有$m-a-b+2$种方案；以此类推，第$k$个$\text{A}$有$m-a-b+k$种插入方案。同时，所有$\text{A}$是本质相同的，所以还要除以$a!$。所以插入$\text{A}$的总方案数就是：$\frac{(m-a-b+1)\cdot(m-a-b+2)\cdots(m-a-b+a)}{a!}={m-b\choose a}$。
因此答案就是：${m-a\choose b}\cdot{m-b\choose a}$。
$T$次求组合数。预处理阶乘和阶乘的逆元即可。
时间复杂度$O(m+T)$。
参考代码（本代码仅供参考，建议添加读入优化）：
```cpp
//problem:P6561
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T>inline void ckmax(T& x,T y){x=(y>x?y:x);}
template<typename T>inline void ckmin(T& x,T y){x=(y<x?y:x);}
const int MAXN=2e6;
const int MOD=998244353;
inline int mod1(int x){return x<MOD?x:x-MOD;}
inline int mod2(int x){return x<0?x+MOD:x;}
inline void add(int& x,int y){x=mod1(x+y);}
inline void sub(int& x,int y){x=mod2(x-y);}
inline int pow_mod(int x,int i){int y=1;while(i){if(i&1)y=(ll)y*x%MOD;x=(ll)x*x%MOD;i>>=1;}return y;}
int fac[MAXN+5],ifac[MAXN+5];
inline int comb(int n,int k){
if(n<k)return 0;
return (ll)fac[n]*ifac[k]%MOD*ifac[n-k]%MOD;
}
void facinit(int lim=MAXN){
fac[0]=1;
for(int i=1;i<=lim;++i)fac[i]=(ll)fac[i-1]*i%MOD;
ifac[lim]=pow_mod(fac[lim],MOD-2);
for(int i=lim-1;i>=0;--i)ifac[i]=(ll)ifac[i+1]*(i+1)%MOD;
}
int m,a,b;
int main() {
facinit();
int T;cin>>T;while(T--){
cin>>m>>a>>b;
int ans = (ll)comb(m-a,b) * comb(m-b,a) % MOD;
cout<<ans<<endl;
}
return 0;
}
```