自动搬运

查看原文

来自洛谷，原作者为

	duyi 大家好我是于之航爸爸

搬运于2025-08-24 22:21:55，当前版本为作者最后更新于2020-07-16 18:19:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

来呀，快活呀↓

超超超超超爽的阅读体验

题目大意

给定三个正整数$m$, $a$, $b$。要求在$[1,2m]$中选出$a$个奇数，$b$个偶数，并且选出的数两两不相邻。问有多少种选择的方案。方案数对$998244353$取模。

$T$组测试数据。

数据范围：$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)$。

参考代码（本代码仅供参考，建议添加读入优化）：

//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;
}