题目题解

问题理解

有 $m$ 个格子（$1$ 到 $m$），$n$ 条线段，第 $i$ 条线段覆盖 $[l_i, r_i]$，以概率 $\frac{p_i}{q_i}$ 存在（独立）。
求每个格子恰好被一条线段覆盖的概率。

---

第一步：问题转化

设 $dp[x]$ 表示前 $x$ 个格子（$1$ 到 $x$）都恰好被一条线段覆盖的概率。
目标：$dp[m]$。

关键观察：要覆盖前 $x$ 个格子，最后一条线段必须覆盖到 $x$，且其左端点为 $l$，则 $[l, x]$ 被该线段覆盖，且 $[1, l-1]$ 必须已被完美覆盖，且 $(l, x]$ 内不能有其他线段存在。

---

第二步：动态规划状态

设 $dp[x]$ 为前 $x$ 个格子恰好被一条线段覆盖的概率。

初始：$dp[0] = 1$（空前缀视为已覆盖）。

对于每个 $x$，考虑所有以 $x$ 为右端点的线段 $i$（$r_i = x$）。
设其左端点为 $l = l_i$，存在概率 $p = \frac{p_i}{q_i}$。

则贡献为：

$$dp[l-1] \times p \times \text{Prob}(\text{区间 } [l, x] \text{ 内无其他线段存在}). $$

---

第三步：计算区间内无其他线段的概率

区间 $[l, x]$ 内的线段分为两类：

1. 左端点在 $l$ 之前，但覆盖到 $[l, x]$：
   这些线段在 $dp[l-1]$ 的计算中已经被强制不存在（否则 $l-1$ 会被多条线段覆盖），因此其存在概率已乘入 $dp[l-1]$，在此不需要额外处理。

2. 左端点在 $[l, x]$ 内：
   这些线段必须都不存在，否则会与当前线段冲突。

因此，我们需要所有左端点在 $[l, x]$ 内的线段都不存在的概率。

设 no[l..x] 表示所有左端点 $j \in [l, x]$ 的线段都不存在的概率乘积。
我们可以预处理前缀积 pref[i] 表示所有左端点 $\le i$ 的线段都不存在的概率乘积。
则区间 $[l, x]$ 的乘积为 $\frac{\text{pref}[x]}{\text{pref}[l-1]}$。

注意：这里“不存在”的概率是 $1 - p$，其中 $p$ 是该线段存在的概率。

---

第四步：转移公式

因此：

$$dp[x] = \sum_{(l, p) \in \text{segments ending at } x} dp[l-1] \cdot p \cdot \frac{\text{pref}[x]}{\text{pref}[l-1] \cdot (1-p)}. $$

解释：分母中的 $(1-p)$ 是因为在 pref[l-1] 中已经乘上了该线段不存在的概率，而我们现在需要的是该线段存在，所以要除掉 $(1-p)$。

---

第五步：预处理

• 对每个位置 $j$，计算 prod[j] 为所有左端点为 $j$ 的线段不存在的概率乘积。
• 计算 pref[i] = pref[i-1] * prod[i]（前缀积）。
• 用 inv 求逆元处理除法。

---

第六步：模运算

由于模数 $998244353$ 是素数，除法用乘法逆元实现。

---

第七步：两种实现

解法一：使用前缀积，需要处理除法（较复杂）。
解法二：在 $dp[0]$ 中直接乘上所有线段不存在的概率，然后在转移时除以 $(1-p)$，实现更简单。

---

代码实现（解法二，推荐）

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

const int MOD = 998244353;

int add(int x, int y) {
    x += y;
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
    return x;
}

int mul(int x, int y) {
    return 1LL * x * y % MOD;
}

int binpow(int x, int y) {
    int z = 1;
    while (y) {
        if (y & 1) z = mul(z, x);
        x = mul(x, x);
        y >>= 1;
    }
    return z;
}

int divide(int x, int y) {
    return mul(x, binpow(y, MOD - 2));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    
    vector<vector<pair<int, int>>> segs(m + 1);
    vector<int> dp(m + 1, 0);
    dp[0] = 1;
    
    for (int i = 0; i < n; i++) {
        int l, r, p, q;
        cin >> l >> r >> p >> q;
        int val = divide(p, q);
        segs[r].emplace_back(l - 1, val);
        dp[0] = mul(dp[0], add(1, -val));  // 乘上该线段不存在的概率
    }
    
    for (int i = 1; i <= m; i++) {
        for (auto [l, p] : segs[i]) {
            int cur = dp[l];
            cur = divide(cur, add(1, -p));  // 去掉 (1-p) 因子
            cur = mul(cur, p);
            dp[i] = add(dp[i], cur);
        }
    }
    
    cout << dp[m] << '\n';
    
    return 0;
}

---

验证样例

输入：

3 3
1 2 1 3
3 3 1 2
1 3 2 3

输出：

610038216

与题目一致。

---

总结

本题的关键在于：

1. 将问题转化为 DP，以右端点为阶段。
2. 用前缀积快速计算区间内无其他线段的概率。
3. 利用模逆元处理分数运算。