P6561 [SBCOI2020] 人

用户头像 发布于 12 小时前 25 次阅读 OI

P6561 [SBCOI2020] 人

考虑把 2i−1, 2i (0<i≤m)2i-1,\ 2i\ (0<i\le m) 放在一起看，那么每组一共有三种情况：

  • A：2i−12i-1 选，2i2i 不选。
  • B： 不选，2i2i 选。
  • C：都不选。

且有一个限制，就是不允许相邻两个组别组成 BA 的形式，因为这样前一组的第二个和后一组的第一个成为了相邻的数，此时不符合题意。

所以我们把问题转化一下，就变成了：有多少种不出现 BA 形式的 A、B、C 组合？

设 A、B 情况分别有 a,ba,b 个，那么 C 情况就有 m−a−bm-a-b 个。

考虑放好 C 以后往相邻的两个 C 之间填 A、B，因为不能出现 BA 形式，所以只能把所有的 A 放在前面，把所有的 B 放在后面。也就是说，A、B 的数量确定时，方案数只有一个。

现在问题就变成了往相邻的两个 C 之间填 A、B 的方案数，由于放 A 与放 B 相互独立，所以可以使用乘法原理。

先考虑往 m−a−bm-a-b 个 C 中填 aa 个 A，一共 m−a−b+1m-a-b+1 个空，每个空可以不填，考虑插板法：

  • xi>0，∑i=1nxi=kx_i>0，\sum^{n}_{i=1} x_i =k 的整数解有 (k−1n−1) \begin{pmatrix} k-1\\n-1 \end{pmatrix} 组。
  • xi≥0，∑i=1nxi=kx_i\ge 0，\sum^{n}_{i=1} x_i =k 的整数解有 (k+n−1n−1) \begin{pmatrix} k+n-1\\n-1 \end{pmatrix} 组。
    解释：将原式转化为 (xi+1)>0，∑i=1n(xi+1)=k+n (x_i+1) > 0，\sum^{n}_{i=1} (x_i+1) =k+n，再使用上面的结论即可。

所以对于 m−a−b+1m-a-b+1 个空填 aa 个，根据第二个结论，有 (m−bm−a−b) \begin{pmatrix} m-b\\m-a-b \end{pmatrix} 种答案。

同理对于 B，有 (m−am−a−b) \begin{pmatrix} m-a\\m-a-b \end{pmatrix} 种答案。

最后根据乘法原理，答案数为 (m−bm−a−b)⋅(m−am−a−b)\begin{pmatrix} m-b\\m-a-b \end{pmatrix} \cdot \begin{pmatrix} m-a\\m-a-b \end{pmatrix}。

对于组合数的计算，发现模数要大于 m,a,bm,a,b 且为质数，所以预处理阶乘与阶乘的逆元即可。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=1e6+5;
const int mod=998244353;
int T;
int m,a,b;
int inv[N],ninv[N];

int mi(int x,int y){
	int res=1;
	while(y){
		if(y&1) (res*=x)%=mod;
		y>>=1,(x*=x)%=mod; 
	}
	return res;
}

int c(int x,int y){
    return inv[x]*ninv[y]%mod*ninv[x-y]%mod;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>T;
	inv[0]=ninv[0]=1;
    for(int i=1;i<N;i++){
		inv[i]=(i*inv[i-1])%mod;
		ninv[i]=(mi(i,mod-2)*ninv[i-1])%mod;
	}
	while(T--){
		cin>>m>>a>>b;
        cout<<c(m-a,m-a-b)*c(m-b,m-a-b)%mod<<"\n";
	}
	return 0;
}