提出 #74718713

---

ソースコード 拡げる

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

typedef long long ll;

const int MAXN = 1000005;
const int N_DP = 105;
const int mod = 998244353;

ll a[MAXN], b[MAXN], sum[MAXN];
ll p[MAXN];
int dp[N_DP][N_DP][N_DP];
int temp_dp[N_DP][N_DP][N_DP];
int next_dp[N_DP][N_DP][N_DP];
ll fact[N_DP], invfact[N_DP];
ll pw[N_DP][N_DP];

ll ksm(ll x, ll p) {
    ll res = 1, item = x % mod;
    while (p) {
        if (p & 1) res = res * item % mod;
        p >>= 1;
        item = item * item % mod;
    }
    return res;
}

void init() {
    fact[0] = 1; 
    invfact[0] = 1;
    for (int i = 1; i < N_DP; i++) {
        fact[i] = fact[i - 1] * i % mod;
        invfact[i] = ksm(fact[i], mod - 2);
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    int rn = n; // 记录原始总数
    
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);

    // 离散化并记录前缀目标数目
    int k = 0;
    for (int i = 1; i <= n; i++) {
        if (i == 1 || a[i] != a[i - 1]) {
            k++;
            b[k] = a[i];
            sum[k] = 1;
        } else {
            sum[k]++;
        }
    }
    for (int i = 1; i <= k; i++) sum[i] += sum[i - 1];
    n = k; // n 更新为不同元素的个数

    b[n + 1] = m + 1;
    ll fm = ksm(m, mod - 2);
    
    // 提前计算好每个区间的命中概率
    for (int i = 1; i <= n; i++) p[i] = (b[i + 1] - b[i]) * fm % mod;
    p[0] = (b[1] - 1) * fm % mod;
    sum[0] = 0;

    // 预处理 EGF 的项 (p[i]^x / x!)
    for (int i = 0; i <= n; i++) {
        ll cur = 1;
        for (int x = 0; x <= rn; x++) {
            pw[i][x] = cur * invfact[x] % mod;
            cur = cur * p[i] % mod;
        }
    }

    memset(dp, 0, sizeof(dp));
    dp[0][0][rn] = 1; // 初始状态: 抽取0次，匹配0次，所有rn个元素均处于活跃等待状态

    // 逆序处理各个区间段
    for (int i = n; i >= 0; i--) {
        memset(temp_dp, 0, sizeof(temp_dp));
        
        // 1. 处理区间门槛（将活跃目标数量卡死在 sum[i] 以内）
        for (int C = 0; C <= rn; C++) {
            for (int M = 0; M <= C; M++) {
                for (int curr_k = 0; curr_k <= rn; curr_k++) {
                    if (dp[C][M][curr_k]) {
                        int next_k = min(curr_k, (int)sum[i]);
                        temp_dp[C][M][next_k] = (temp_dp[C][M][next_k] + dp[C][M][curr_k]) % mod;
                    }
                }
            }
        }

        memset(next_dp, 0, sizeof(next_dp));
        
        // 2. 在当前区间进行 x 次独立抽取
        for (int C = 0; C <= rn; C++) {
            for (int M = 0; M <= C; M++) {
                for (int curr_k = 0; curr_k <= sum[i]; curr_k++) {
                    ll val = temp_dp[C][M][curr_k];
                    if (!val) continue;

                    // 优化：将 x 分段，避免在内层循环做 min 判断
                    // 情况 A: x <= curr_k (所有抽取都转为了有效匹配)
                    for (int x = 0; x <= curr_k && C + x <= rn; x++) {
                        next_dp[C + x][M + x][curr_k - x] = (next_dp[C + x][M + x][curr_k - x] + val * pw[i][x]) % mod;
                    }
                    // 情况 B: x > curr_k (匹配已达上限，剩下的抽取全部打水漂)
                    for (int x = curr_k + 1; C + x <= rn; x++) {
                        next_dp[C + x][M + curr_k][0] = (next_dp[C + x][M + curr_k][0] + val * pw[i][x]) % mod;
                    }
                }
            }
        }
        memcpy(dp, next_dp, sizeof(dp));
    }

    // 统计各个匹配次数的概率并输出
    for (int i = 0; i <= rn; i++) {
        ll ans = 0;
        for (int curr_k = 0; curr_k <= rn; curr_k++) {
            ans = (ans + dp[rn][i][curr_k]) % mod;
        }
        // 乘回 n! (即 rn!) 恢复成排列总权重
        ans = ans * fact[rn] % mod; 
        cout << ans << " ";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    init(); // 初始化阶乘表
    
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

提出情報

ジャッジ結果