收音机

本题要求计算在随机播放模式下，在时刻 $X+0.5$ 秒时，第1首曲子正在播放的概率。注意，由于曲目连续播放且每首曲子都是完整播放，播放时刻总是累加各曲目时长。设当前累积播放时间为 $S$，若下一首曲子为第1首且其时长为 $T_1$，要使得第1首曲子正在播放，则需要满足

$$S \le X + 0.5 < S + T_1$$

由于 $S$ 为整数，而 $X+0.5$ 总落在两个整数之间，可以转换为

$$S \le X \quad \text{且} \quad S > X - T_1$$

也就是 $S\in [\max(0, X-T_1+1),, X]$。因此，题目的求解思路转化为：

1. 计算所有可能的播放序列，其总播放时长恰好为 $S$ 秒的概率，其中 $S$ 从 $0$ 到 $X$ 之间；
2. 对于满足 $S\in [\max(0, X-T_1+1),, X]$ 的状态，若下一首歌选中第1首的概率为 $\frac{1}{N}$（因为随机选取），则累加这些状态的概率乘以 $\frac{1}{N}$。

我们注意到，给定每首歌的选择概率都是 $\frac{1}{N}$，因此在进行状态转移时，每加入一首歌曲都乘以 $\frac{1}{N}$。另外，为了求得最终的概率模 $998244353$，需要利用快速幂求模逆元的技巧，即求出 $n^{-1} \pmod{998244353}$。总体来说，本题通过状态动态规划（DP）的方式累积所有可能的播放序列，并利用概率转移来计算精确的概率，最后再乘以一个额外的 $\frac{1}{N}$ 来确保下一首歌为第1首。

该方法的核心在于将连续随机过程转化为求和问题，每个状态的概率由前面状态转移而来。数学公式部分，我们需要求出下列概率的和：

$$P = \frac{1}{N}\sum_{S=\max(0, X-T_1+1)}^{X} f(S)$$

其中 $f(S)$ 表示累积时间恰好为 $S$ 的概率，而 $f(S)$ 通过状态转移满足

$$f(S)=\sum_{j=1}^{N} \frac{1}{N} \cdot f(S-T_j) \quad \text{(当 } S\ge T_j\text{)} $$

由于 $f(0)=1$，即初始状态的概率为 1。

算法采用动态规划（DP）思想。我们定义一维数组 $f[i]$ 表示经过一系列曲目之后，总播放时长恰好为 $i$ 秒的概率。初始状态为 $f[0]=1$。由于每次播放选择曲目概率均为 $\frac{1}{N}$，状态转移方程可以写为

$$f[i] = \sum_{j=1}^{N} \frac{1}{N}\cdot f[i-T_j] \quad \text{对于 } i \ge T_j $$

在实际实现时，我们将 $\frac{1}{N}$ 转换为模 $998244353$ 意义下的乘法逆元，记为 $ni$。因此，状态转移公式便变为

$$f[i] = \sum_{j=1}^{N} \left( f[i-T_j] \cdot ni \right) \pmod{998244353} $$

我们遍历 $i$ 从 $0$ 到 $X$，对每个 $i$，遍历所有曲目 $j$（$1 \le j \le N$），如果 $i \ge T_j$，则更新状态 $f[i]$。在所有状态转移完成后，我们需要统计所有满足

$$i \in [\max(0, X-T_1+1), X]$$

的 $f[i]$。这里的区间表示：若前面的曲目累计时间 $i$ 在这个区间内，则下一首曲目（若为第1首）能够覆盖时刻 $X+0.5$。最后答案为上面和再乘以一次 $\frac{1}{N}$（即 $ni$），得到最终概率值。

整个过程在模 $998244353$ 下计算，因此每一步计算都做模运算，避免大数问题。同时，为了计算模逆元，我们使用快速幂算法，该算法的数学公式为

$$a^{-1} \equiv a^{p-2} \pmod{p}$$

这里 $p=998244353$ 是素数。这样能确保逆元计算在对数时间内完成，从而保证整体算法的时间复杂度在允许范围内。

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

typedef long long ll;

const ll MOD = 998244353;
ll f[20000], t[20000];

ll qp(ll x, ll y) {
    ll ret = 1;
    while (y) {
        if (y & 1) {
            ret = (ret * x) % MOD;
        }
        x = (x * x) % MOD;
        y >>= 1;
    }
    return ret;
}

int main() {
    ll n, x;
    cin >> n >> x;
    
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }

    f[0] = 1;
    ll ni = qp(n, MOD - 2);

    for (int i = 0; i <= x; i++) {
        for (int j = 1; j <= n; j++) {
            if (i >= t[j]) {
                f[i] = (f[i] + f[i - t[j]] * ni) % MOD;
            }
        }
    }

    ll ans = 0;
    for (int i = max(0LL, x - t[1] + 1); i <= x; i++) {
        ans = (ans + f[i]) % MOD;
    }

    cout << (ans * ni) % MOD;
    return 0;
}

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static final long MOD = 998244353;
    
    // 快速幂求逆元函数
    static long qp(long x, long y) {
        long ret = 1;
        while (y > 0) {
            if ((y & 1) == 1) {
                ret = ret * x % MOD;
            }
            x = x * x % MOD;
            y >>= 1;
        }
        return ret;
    }
    
    public static void main(String[] args) throws IOException {
        // 输入输出加速，统一按 token 读取
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 读取所有输入token
        int n = Integer.parseInt(st.nextToken());
        int X;
        if (st.hasMoreTokens()) {
            X = Integer.parseInt(st.nextToken());
        } else {
            X = Integer.parseInt(br.readLine().trim());
        }
        
        long[] t = new long[n + 1];
        // 若后续token不足则继续读取下一行
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(br.readLine());
            }
            t[i] = Long.parseLong(st.nextToken());
        }
        
        // 定义dp数组，时间范围为 0~X
        long[] f = new long[X + 1];
        f[0] = 1;
        long ni = qp(n, MOD - 2);  // 计算1/n的逆元
        
        // 动态规划状态转移
        for (int i = 0; i <= X; i++) {
            for (int j = 1; j <= n; j++) {
                if (i >= t[j]) {
                    f[i] = (f[i] + f[i - (int)t[j]] * ni) % MOD;
                }
            }
        }
        
        // 统计所有满足 [max(0, X-t[1]+1), X] 的状态
        long ans = 0;
        int start = Math.max(0, X - (int)t[1] + 1);
        for (int i = start; i <= X; i++) {
            ans = (ans + f[i]) % MOD;
        }
        // 乘上选中第一首曲子的概率
        out.println(ans * ni % MOD);
        out.flush();
        out.close();
        br.close();
    }
}

import sys
input = sys.stdin.readline
MOD = 998244353

def qp(x, y):
    ret = 1
    while y:
        if y & 1:
            ret = ret * x % MOD
        x = x * x % MOD
        y //= 2
    return ret

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    X = int(data[1])
    t = [0] * (n + 1)
    for i in range(1, n+1):
        t[i] = int(data[i+1])
    
    f = [0] * (X + 1)
    f[0] = 1
    ni = qp(n, MOD - 2)  # 1/n 的逆元
    
    for i in range(0, X + 1):
        for j in range(1, n + 1):
            if i >= t[j]:
                f[i] = (f[i] + f[i - t[j]] * ni) % MOD
    
    ans = 0
    start = max(0, X - t[1] + 1)
    for i in range(start, X + 1):
        ans = (ans + f[i]) % MOD
    sys.stdout.write(str(ans * ni % MOD))
    
if __name__ == "__main__":
    main()