收音机 本题要求计算在随机播放模式下，在时刻 $X+0.5$ 秒时，第1首曲子正在播放的概率。注意，由于曲目连续播放且每首曲子都是完整播放，播放时刻总是累加各曲目时长。设当前累积播放时间为 $S$，若下一首曲子为第1首且其时长为 $T_1$，要使得第1首曲子正在播放，则需要满足 $$ S \le X + 0.5 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$ 是素数。这样能确保逆元计算在对数时间内完成，从而保证整体算法的时间复杂度在允许范围内。 ```cpp #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; } ``` ```java 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(); } } ``` ```python 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() ```