题解
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;
}