提出 #75214412

---

ソースコード 拡げる

#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;

mt19937_64 rng(std::chrono::system_clock::now().time_since_epoch().count());

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);
}
signed main() {
    cin.tie(0)->sync_with_stdio(0); precalc();
    int t;
    cin >> t;
    while(t--){
        int n,c;
        cin >> n >> c;
        vector<int>a(n+2);
        for(int i = 1; i<=n; i++){
            cin >> a[i];
        }
        a[n+1] = c+1;
        sort(all(a));
        vector<vector<vi>>dp(n+1,vector<vi>(n+1,vi(n+1)));
        int ic = inverse(c);
        if(a[1] != 1){
            int p = (a[1] - 1) * ic % mod;
            vector<int>pw(n+1); pw[0] = 1;
            for(int i = 1; i<=n; i++){
                pw[i] = pw[i-1] * p % mod;
            }
            for(int j = 0; j<=n; j++){
                dp[0][0][n-j] = choose(n,j) * pw[j] % mod;
            }
        }
        else{
            dp[0][0][n] = 1;
        }
        for(int i = 1; i<=n; i++){
            int p = fix(a[i+1] - a[i]) * ic % mod;
            vector<int>pw(n+1);
            pw[0] = 1;
            for(int j = 1; j<=n; j++){
                pw[j] = pw[j-1] * p % mod;
            }
            for(int j = 0; j<n; j++){
                for(int k = 0; k<=n; k++){
                    for(int d = 0; d<=k; d++){
                        int pr = pw[d] * choose(k,d) % mod;
                        int nj = max(0ll,j+1 - d);
                        dp[i][nj][k-d] += dp[i-1][j][k] * pr; dp[i][nj][k-d] %= mod;
                    }
                }
            }
        }
        for(int r = n; r>=0; r--){
            cout << dp[n][r][0] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

提出情報

ジャッジ結果