关于一种计数的讨论、ARC212C Solution

在 Print 之前

在 ARC212C 中，我们遇到了一种形如：

已知：

$$\sum _{i=0} ^{m} x_i=k$$

求所有：

$$\prod _{i=0} ^{m} x_i$$

的和的题，这引发我们对组合数学的进一步思考。

原式化简

我们可以注意到，如果想要 $\prod _{i=0} ^{m} x_i$ 产生贡献，那么 $\forall x_i$ 都不能为 0 。

由此我们可以将题面转化一下，可以理解为将 $k$ 个球放入 $m$ 个盒子中，且盒子内不为空，求每个盒子选出一个球的方案数。

可以考虑插板法，我们发现，选出来的 $m$ 个球与所插 $m-1$ 个板是交替出现的，由此我们可以把它们一起视作板，这样下来就将题目再次转化为了在 $k-m$ 个球中插入 $2 \times m-1$ 个板。

即原题的答案是：

$$\binom {k+m-1}{2 \times m-1}$$

例题（ARC212C）

题目

有白球。首先，你把每个球涂成红色或蓝色。

然后，你把这些 $n$ 红色或蓝色的彩绘球放在 $m$ 可区分的盒子里。

设 $a_i$ 和 $b_i$ 分别为 $i$ \第1个盒子中红色球和蓝色球的个数。

求出 $\prod_{1\leq i \le m}|a_i-b_i|$ 对所有放置球的方式取模 $998244353$ 的和。

这里，两种放置球的方法是不同的，当且仅当 $a_i$ 和 $b_i$ 中至少有一个对于某些 $i$ 是不同的。

特别是，球彼此之间是无法区分的。

Solution

我们发现一种分配的方案产生的贡献是 $a_i$ 和 $b_i$ 的差的绝对值，所以考虑先从 $n$ 个球中选出 $i$ 个球（$i$ 为偶数），分成 $i \div 2$ 组，每组为一红一蓝，这些球是不会做出贡献的，那么把它分在 $m$ 个盒子里的方案数是 $\binom {i \div 2 + m-1}{m-1}$（其实就是插板法）。

剩下 $n-i$ 个白色小球要放在 $m$ 个篮子里面，且在同一篮子里的白色小球颜色一致。

其实就是

已知：

$$\sum _{i=0} ^{n} x_i=n-i$$

求所有：

$$\prod _{i=0} ^{n} x_i$$

的和。

只不过需注意的是每个篮子中可以有两种染色方案，所以最终答案乘一个 $2^m$ 即可。

最终答案就是：

$$\sum _{i=0}^{n} \binom {i \div 2 + m-1}{m-1} \times \binom {n-i+m-1}{2 \times m-1} \times 2^m \ [i \equiv 0 \mod 2]$$

Code

#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef int praise_long_long;
namespace io {
    using namespace std;
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f*=(-1);
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans*=10;
            ans+=(x-'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=2e7+5,mod=998244353,inf=2e18;
const ld eps=1e-6;
ll n,m,sum[N],inv[N],ans;
inline void init () {
    inv[0]=inv[1]=1;
    for (ll i=2;i<=N-5;i++) {
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
    sum[0]=1;
    for (ll i=1;i<=N-5;i++) {
        inv[i]*=inv[i-1];
        sum[i]=sum[i-1]*i;
        sum[i]%=mod;
        inv[i]%=mod;
    }
}
inline ll C (ll x,ll y) {
    if (x<y||y<0) {
        return 0;
    }
    return sum[x]*inv[y]%mod*inv[x-y]%mod;
}
inline ll qpow (ll x,ll y) {
    ll cnt=1;
    while (y) {
        if (y&1) {
            cnt*=x;
            cnt%=mod;
        }
        x*=x;
        x%=mod;
        y>>=1;
    }
    return cnt;
}
inline void solve () {
    n=read(),m=read();
    for (ll i=0;i<=n;i+=2) {
        ll num=n-i;
        ans+=C((i>>1)+m-1,m-1)%mod*C(num+m-1,m*2-1)%mod;
        ans%=mod;
    }
    print(ans*qpow(2,m)%mod);
}
praise_long_long main () {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll T=1;
    // T=read();
    init();
    while (T--) {
        solve();
    }
    return 0;
}
/**/