ABC405E

zhuoheng · 2025-05-11 09:46:57 · 题解

这题第一眼看上去就数学。
首先我们需要做在 a+b 里放置 a 个相同的物品和b个相同的物品的不同情况数。
这个的很显然等同于在 a+b 个空位中放 a 个物品的组合数，即 C^{a+b}_{a} 。
接着我们从头考虑这个问题，苹果和橙子肯定是放在最开始的，但是它们之间的顺序是不确定的所以需要计算一下。
接着我们来看橙子，它被要求在葡萄之后，但是它和香蕉的顺序是不固定的。
然后看到葡萄，它被要求在橙子和苹果之后，所以相当于确定了苹果和橙子后它就基本上固定了，但是它和香蕉的顺序也是不固定的。
那么我们可以发现只需要枚举一下有多少个橙子在苹果之后然后就相当于在确定的橙子和葡萄中放置橙子。
这题就做完了。自认为思路比较清新。
放个代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353,N=4e6;
int qpow(int a,int b){
    int res=1;a%=mod;
    while(b){
        if(b%2)res=res*a%mod;
        a=a*a%mod,b>>=1;
    }
    return res;
}
int A[N+1],inva[N+1];
int C(int a,int b){
    if(!a||!b)return 1;
    return A[a+b]*inva[a]%mod*inva[b]%mod;
}
int a,b,c,d,ans;
signed main(){
    A[0]=1,A[1]=1;
    for(int i=1;i<=N;i++)A[i]=A[i-1]*i%mod,inva[i]=qpow(A[i],mod-2);
    cin>>a>>b>>c>>d;
    for(int i=0;i<=b;i++)ans+=C(a-1,i)*C(b+d-i,c)%mod,ans%=mod;
    cout<<ans;

}

注意代码中的 C 函数并不等同于组合数。