【2023NOI模拟赛11】發 做题记录

你在打游戏。在这个游戏中你有一个怒气值，其初始为 $A$，你的目标是通过 $N$ 次操作将其变为 $B$。这 $N$ 次操作决定了你在一次游戏中的得分，这个得分初始为 $1$，每次操作你可以：

• 发怒，这会使你怒气值 $+1$，然后将得分乘上当前怒气值。
• 冷静，这会使你怒气值 $−1$，而不改变得分。

你想知道如果你使用所有能够达成目标的操作序列都各进行一次游戏，你的得分总和会是多少。特别地，如果无论如何都无法达成目标，则总和为 $0$。由于这个总和可能很大，所以你只想得到其对 $998244353$ 取模后的结果。请你帮帮你自己求出答案！

$0\le N,A,B\le 2\times 10^7$。

首先 $N+A+B$ 若不为偶数就不存在可以达成目标的操作序列，直接输出 $0$。

观察到由于 $0\le A,B$，所以若怒气值降到负数则之后一定升到 $0$，让得分为 $0$。所以若把发怒看作 (，冷静看作 )，那么在操作序列对应的括号序列前面加上 $A$ 个 (，后面加上 $B$ 个 ) 则这个括号序列一定合法。

考虑 $A=B=0$ 的情况，发现答案为 $1\times 3\times 5\times...\times (N-1)=(N-1)!!$。这个东西有个组合意义：$N$ 个互不相同的东西分成 $\frac{N}{2}$ 个互不区分的无序二元组的方案数。那么考虑构建双射，对于一种分组方案，在这一组中小的那个位置填上 (，大的那个位置填 )，则这样填出来的一定是合法括号序列。

考虑一个括号序列有多少种分组方案与之对应。可以从右向左考虑，遇到 ) 就先加入一个集合 $S$，遇到 ( 就随便从 $S$ 中选一个位置和它组成一个二元组。设某一次遇到 ( 的位置为 $i$，所以 $|S|$ 就是 $i$ 之后 ) 的个数 $cnt)_{[i+1,n]}$ 减掉 $i$ 之后 ( 的个数 $cnt(_{[i+1,n]}$；那么由于 $A=B=0$，所以 $cnt(_{[1,i]}-cnt)_{[1,i]}=cnt)_{[i+1,n]}-cnt(_{[i+1,n]}=|S|$。因为一个括号序列的分组方案数是 $\prod|S|$，所以一个括号序列对应的分组方案就是它的分数！

加上 $A$ 和 $B$ 的条件，问题就变成了：

有 $A+N+B$ 个元素，现在要把它们两两配对成 $\frac{A+N+B}{2}$ 个互不区分的无序二元组，求满足以下条件的配对方案个数：

• $A$ 中的元素不能两两配对；
• $B$ 中的元素不能两两配对；

如果只有 $B$ 中元素不能两两配对的限制那么很好做，答案即为 $(N+A)^{\underline{B}}(N+A-B-1)!!$，即最后 $B$ 个元素的配对方案乘上剩下 $N+A-B$ 个元素的配对方案。若考虑上 $A$ 的限制其实也很简单，只需要枚举有多少个二元组是 $A$ 中元素互相配对的就行了：

$\frac{1}{A!}\sum\limits_{i=0}^{\lfloor\frac{A}{2}\rfloor}(-1)^i\binom{A}{2i}(2i-1)!!(N+A-2i)^{\underline{B}}(N+A-2i-B-1)!!$

乘上 $\frac{1}{A!}$ 是为了去掉在括号前面添加的那 $A$ 个 ( 的贡献。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=40000005;
const int p=998244353;

int n,a,b;
int fra[S],inv[S],fra2[S];

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

inline int C(int n,int m)
{
	if(n<0||m<0||n<m) return 0;
	return 1ll*fra[n]*inv[n-m]%p*inv[m]%p;
}

int main()
{
	freopen("fa.in","r",stdin);
	freopen("fa.out","w",stdout);
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
	inv[S-3]=qpow(fra[S-3],p-2);
	for(int i=S-3;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
	fra2[0]=fra2[1]=1;
	for(int i=2;i<=S-3;i++) fra2[i]=1ll*fra2[i-2]*i%p;
	scanf("%d%d%d",&n,&a,&b);
	if(n+a+b&1) return puts("0"),0;
	int ans=0;
	for(int i=0;i*2<=a&&n+a-i*2>=b;i++)
	{
		int val=1ll*C(a,i*2)*(i==0?1:fra2[i*2-1])%p;
		val=1ll*val*fra[n+a-i*2]%p*inv[n+a-i*2-b]%p;
		val=1ll*val*(n+a-i*2-b==0?1:fra2[n+a-i*2-b-1])%p;
		if(i&1) ans=(ans-val+p)%p;
		else ans=(ans+val)%p;
	}
	ans=1ll*ans*inv[a]%p;
	printf("%d\n",ans);
	return 0;
}