Submission #75559531

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int ll

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MXN = 2000000;
vector<int>fact(MXN+10);
vector<int>inv(MXN+10);
const int mod = 998244353;
int modpow(int x, int y) {
    return !y?1:((y % 2 ? x : 1) * modpow((x * x) % mod, y / 2)) % mod;
}
int choose(int x, int y){
    if(y>x || x < 0 || y < 0)return 0;
    return (fact[x]*inv[y]%mod)*inv[x-y]%mod;
}
int permute(int x, int y){
    if(y>x || x < 0 || y < 0)return 0;
    return (fact[x]*inv[x-y])%mod;
}
void precalc(){
    fact[0] = 1; inv[0] = 1;
    for(int i = 1; i<=MXN; i++){
        fact[i] = fact[i-1]*i%mod;
    }
    inv[MXN] = modpow(fact[MXN],mod-2);
    for(int i = MXN-1; i>0; i--){
        inv[i] = inv[i+1]*(i+1)%mod;
    }
}
int fix(int x){
    x%=mod;
    if(x<0)x+=mod;
    return x;
}
int inverse(int x){
    return modpow(x,mod-2);
}
int starsbars(int n, int k){
    return choose(n+k-1,k-1);
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false); precalc();
    int n,L,R;
    cin >> n >> L >> R;
    vi f(n+1);
    int m = 0;
    for(int i = 1; i<=n; i++){
        int x;
        cin >> x;
        m = max(m,x);
        f[x]++;
    }
    vector<vector<vi>>dp(n+1,vector<vi>(n+1,vi(n+1)));
    dp[m][1][1] = 1;
    int cur = f[m];
    for(int i = m-1; i>=1; i--){
        rep(j,0,n) rep(k,0,n) rep(l,0,2) rep(r,0,2){
            if(l + r > f[i])continue;
            int items = f[i] - l - r;
            int buckets = cur - 1 + l + r;
            dp[i][j+l][k+r] += dp[i+1][j][k] * starsbars(items,buckets) % mod;
            dp[i][j+l][k+r] %= mod;
        }
        cur += f[i];
    }
    cout << dp[1][L][R] << '\n';
    return 0;
}

Submission Info

Judge Result