ABC458_E 题解

· · 题解

观前提示

本文采用折叠框写法，如果您想部分独立思考又没有头绪，十分建议您观看。

题目大意

给你 a、b、c，让你求出恰好包含 a 个 1、b 个 2 和 c 个 3 且满足相邻两项绝对值之差不大于一的序列的个数。

题目中的 X_1 为 a，X_2 为 b，X_3 为 c。

思路

:::info[Hint 1] 注意到只有三个数，所以绝对值之差大于 1 的只有 1 和 3 相邻时才会出现。 :::

:::info[Hint 2] 那么我们考虑先把所有的 2 都放下来，之间的空隙插入 1 和 3。 :::

:::info[Hint 3] 总共有 b+1 个空隙，我们可以选择 i 个空隙放入 1 和 k 个空隙放入 3，注意可以不填满，但不能让 i 或 k 等于 0。

如果有 n 个相同数字要放入到 m 个不同空隙中，就有 \binom{n-1}{m-1} 种选择，也就是隔板法。 :::

:::info[Hint 4] 令 j=b-i+1，也就是选完 i 个后还剩多少个空隙。

选择 i 个空隙放入 1、选择 k 个空隙放入 3 时，对答案的贡献为

\binom{b+1}{i} \cdot \binom{a-1}{i-1} \cdot \binom{j}{k} \cdot \binom{c-1}{k-1}

组合数可以通过预处理逆元、阶乘快速计算。 :::

:::info[Hint 5] 时间复杂度仍需优化。

注意到式子可以被拆成前后两个部分（无关联性），对于相同的前半部分，后半部分为

\sum_{k=1}^{\min(c,j)} \binom{j}{k} \cdot \binom{c-1}{k-1}

利用对称恒等式变换

\sum_{k=1}^{\min(c,j)} \binom{j}{k} \cdot \binom{c-1}{c-k}

然后用范德蒙德卷积公式，带入 r=j，s=c-1，n=c，得到

\binom{j+c-1}{c}

把它放回原式，最终答案就是所有的

\binom{b+1}{i} \cdot \binom{a-1}{i-1} \cdot \binom{j+c-1}{c}

之和，这个可以线性求。 :::

代码

:::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls p<<1
#define rs p<<1|1
#define pb push_back

const ll N=3e6+10;
const ll M=2e3+10;
const ll inf=1e12;
const ll mod=998244353;

inline ll lowbit(ll x){
    return x&(-x);
}ll fac[N],inv[N];
inline ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res*=a;
            res%=mod;
        }
        a*=a;
        a%=mod;
        b>>=1;
    }
    return res;
}
inline ll C(ll n,ll m){
    ll res=fac[n];
    res*=inv[m];
    res%=mod;
    res*=inv[n-m];
    res%=mod;
    return res;
}
ll a,b,c;

ll ans=0;

int main(){
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    fac[0]=1;
    for(int i=1;i<=3000000;i++){
        fac[i]=fac[i-1]*i;
        fac[i]%=mod;
    }
    inv[3000000]=qpow(fac[3000000],mod-2);
    for(int i=3000000-1;i>=0;i--){
        inv[i]=inv[i+1]*(i+1);
        inv[i]%=mod;
    }
    cin>>a>>b>>c;
    for(int i=1;i<=min(a,b);i++){
        ll j=b-i+1;
        ll tmp=C(b+1,i);
        tmp*=C(a-1,i-1);tmp%=mod;
        ll tmp2=C(j+c-1,c);
        ans+=(tmp*tmp2)%mod;
        ans%=mod;
    }
    cout<<ans<<'\n';
    return 0;
}

:::