关于一种计数的讨论、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;
}
/**/