题解：AT_abc405_e [ABC405E] Fruit Lineup

Jenny_yu · 2025-05-11 22:01:12 · 题解

是道数学题。

设 n = A + B + C + D。根据题目条件能想出来大概水果应该这么排。

这样的排法初步保证了苹果和橙子都排在葡萄前。

为什么要单独把第一个葡萄的位置列出来？因为第一个葡萄的位置确定后，橙子和苹果的位置区间就定了。因此考虑枚举第一个葡萄的位置。

前 i - 1 个水果，先排橙子，情况有 \binom{i - 1}{B} 种。之后从前往后找空位先把苹果都填了，剩余还有位置就填香蕉。这样保证了苹果排在香蕉前。

之后还要考虑葡萄和香蕉的区间。一共 n - i 个位置，还没排位置的葡萄有 D - 1 个，因此情况数有 \binom{n - i}{D - 1} 种。

因此对于 A + B + 1 \le i \le n - D + 1 的 i，贡献有 \binom{i - 1}{B} \binom{n - i}{D - 1}。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int s[4000010];
int poww(int x,int y){
    int res = 1;
    while(y){
        if(y % 2 == 1)res = res * x % mod;
        x = x * x % mod;
        y /= 2;
    }
    return res;
}
int C(int n,int m){
    return s[m] * poww(s[n],mod - 2) % mod * poww(s[m - n],mod - 2) % mod;
}
signed main(){
    int a,b,c,d;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    int ans = 0;
    s[0] = 1;
    for(int i = 1; i <= a + b + c + d; i++){
        s[i] = s[i - 1] * i % mod;
    }
    for(int i = a + 1 + b; i <= a + b + c + 1; i++){
        ans = (ans + C(b,i - 1) * C(d - 1,a + b + c + d - i) % mod) % mod;
    }
    printf("%lld",ans);
    return 0;
}