[ARC212C] ABS Ball题解

题解

1.题目

有 $N$ 个白球。首先，你需要将每个球涂成红色或蓝色。

然后，你将这 $N$ 个已被涂成红色或蓝色的球放入 $M$ 个可区分的盒子之中。

设 $a_i$ 和 $b_i$ 分别表示第 $i$ 个盒子中红球和蓝球的数量。

请你求出所有放球方式中$\prod\limits_{1 \leq i \leq M} |a_i - b_i|$的和，对 $998244353$ 取模。

2.思路

首先我们可以从配对 出发

因为题目是$\prod\limits_{1 \leq i \leq M} |a_i - b_i|$，

可以看成是每个箱子已经配对了$\min {a_i,b_i}$对小球后再在剩下的小球中选出一个小球的方案数

这就十分的方便了，先考虑配对的方案数

可以先枚举有 $k$ 个配对

那么要将 $k$ 个配对分配到 $m$ 个箱子中（注意配对数可以为空，只是球数不能为空），

所以用隔板法：$C_{k+m-1}^{m-1}$

接下来，讨论每个箱子中剩下的球

首先，剩下的球有可能是蓝色或者红色

所以每个箱子都有可能出现两种剩余情况

所以这里有 $2^m$ 种方案

然后，讨论要从每个箱子中选出一个球

这里是最难理解的

首先，我们需要把剩下的 $n-2k$ 个球分配到 $m$ 个箱子中（不能有空箱子）

再然后，我们需要在每个箱子中选出一个球
可以看作在每个箱子内又有一个隔板（这个隔板在球上，代表选了这个球）

所以总结一下：

• 可插的隔板位置数：$n-2k-1+m$ （分配小球的隔板数+箱子内那个选球的隔板数）
• 要插的隔板数： $m-1+m$ (分配小球的隔板数+箱子内那个选球的隔板数)
  于是便推出了这部分的式子 $C_{n-2k-1+m}^{2m-1}$

综上，根据乘法原理，答案为 $\Sigma_{k=0}^{\frac{n+m-1}{2}} {2^m C_{k+m-1}^{m-1} C_{n-2k-1+m}^{2m-1}}$

3.Code

#include<bits/stdc++.h>
#define int long long
const int mod=998244353;
using namespace std;
int n,m,siz[30000010],fac[30000010],inv[30000010];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        b>>=1;
        a=a*a%mod;
    }//cout<<res<<endl;
    return res;
}
void pre(int N){
    fac[0]=inv[0]=1;
    for(int i=1;i<=N;i++)fac[i]=i*fac[i-1]%mod;
    inv[N]=qpow(fac[N],mod-2);
    for(int i=N-1;i>=1;i--)inv[i]=(i+1)*inv[i+1]%mod;
}int ans=0;
int C(int n,int m){
    if(n<0 or m<0 or n-m<0)return 0;
    return fac[n]*inv[n-m]%mod*inv[m]%mod;
}

main(){
    cin>>n>>m;
    pre(30000000);
    for(int i=0;2*i<=n+m-1;i++){
        ans+=C(i+m-1,m-1)*C(n+m-1-2*i,2*m-1)%mod*qpow(2ll,m)%mod;
        ans%=mod;
    }cout<<ans;
    return 0;
}