题解：AT_abc458_e [ABC458E] Count 123

ysw_2029 · 2026-05-19 11:58:26 · 题解

永远找不到原题的典题系列。

注意到 1 和 3 不能相邻，考虑按照 2 的数量将整个数列分为 X_2+1 段区间。

考虑枚举这 X_2+1 段中有多少段中含有至少一个 1。设枚举到有 i 段，则从这 X_2+1 段里选 i 段的方案数为 \begin{pmatrix}X_2+1\\i\\\end{pmatrix}，往这 i 段里放 X_1 个 1 且每段至少有一个 1 的方案数为 \begin{pmatrix}X_1-1\\i-1\\\end{pmatrix}，往剩下的 X_2-i+1 段里放 X_3 个 3 且可以有没有放的段的方案数为 \begin{pmatrix}X_3+X_2-i\\X_2-i\\\end{pmatrix}。也就是说，如果枚举到 i 段，则方案数为以上三个组合数的乘积。

所以答案就为 \sum\limits_{i=1}^{X_2}\begin{pmatrix}X_2+1\\i\\\end{pmatrix}\begin{pmatrix}X_1-1\\i-1\\\end{pmatrix}\begin{pmatrix}X_3+X_2-i\\X_2-i\\\end{pmatrix}，预处理组合数然后直接计算即可。

:::success[AC code]

#include<bits/stdc++.h>
#define int long long
using namespace std
constexpr int N=3000002,mod=998244353;
inline int mypow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        a=a*a%mod,b>>=1;
    }
    return ans;
}
int fac[N],inv[N];
inline int C(int n,int m)
{
    if(n<m)return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline void init()
{
    fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
    inv[N-1]=mypow(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i++)inv[i]=inv[i+1]*(i+1)%mod;
}
int n1,n2,n3,ans;
signed main()
{
    init();
    cin>>n1>>n2>>n3;
    for(int i=1;i<=n2;i++)
        ans=(ans+C(n2+1,i)*C(n1-1,i-1)%mod*C(n3+n2-i,n2-i))%mod;
    cout<<ans;
    return 0;
}

:::