为了解决这个问题，我们需要计算每个单元格恰好被一个线段覆盖的概率。线段独立存在，每个线段存在的概率为 \( \frac{p_i}{q_i} \)。要求每个单元格必须被覆盖且仅被一个线段覆盖，因此存在的线段必须恰好覆盖整个区间 \([1, m]\) 且互不重叠（可以相邻）。

方法思路

1. 问题分析：问题要求所有线段的存在性组合使得每个单元格被恰好一个线段覆盖。这意味着线段必须形成整个区间 \([1, m]\) 的一个无重叠且无间隙的划分。任何不在划分中的线段必须不存在，否则会导致某些单元格被多个线段覆盖或未被覆盖。
2. 关键观察：每个线段独立存在，因此总概率是所有划分方案的概率之和。每个划分方案 \( S \) 的概率为： \(\left( \prod_{i \in S} \frac{p_i}{q_i} \right) \times \left( \prod_{i \notin S} \left(1 - \frac{p_i}{q_i}\right) \right)\)
3. 数学变换：将概率表达式转化为： \(\left( \prod_{i=1}^{n} \left(1 - \frac{p_i}{q_i}\right) \right) \times \left( \prod_{i \in S} \frac{\frac{p_i}{q_i}}{1 - \frac{p_i}{q_i}} \right)\) 定义 \( a_i = \frac{p_i}{q_i} \) 和 \( b_i = \frac{a_i}{1 - a_i} \)，则总概率为常数 \( C = \prod_{i=1}^{n} (1 - a_i) \) 乘以所有划分方案 \( S \) 的 \( \prod_{i \in S} b_i \) 之和。
4. 动态规划：使用动态规划计算所有划分方案的 \( \prod_{i \in S} b_i \) 之和。定义 \( dp[i] \) 为覆盖区间 \([1, i]\) 的划分方案的 \( \prod b_i \) 之和。转移方程为： \(dp[i] = \sum_{\text{线段 } k: r_k = i} dp[l_k - 1] \times b_k\) 其中 \( l_k \) 和 \( r_k \) 分别是线段 \( k \) 的左右端点。
5. 优化：预处理每个右端点对应的线段，以便在动态规划中快速访问。常数 \( C \) 通过一次遍历计算，动态规划从 \( dp[0] = 1 \) 开始逐步计算到 \( dp[m] \)。

解决代码

#include <bits/extc++.h>
#define endl '\n'
typedef long long ll;
#define int ll
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

constexpr int mod = 998244353;

inline int fpow(int a, int x) {
  int res = 1;
  while (x) {
    if (x & 1) {
      (res *= a) %= mod;
    }
    (a *= a) %= mod;
    x >>= 1;
  }
  return res % mod;
}

inline int inv(const int a) { return fpow(a, mod - 2); }

void Main() {
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> seg(m + 1);
  vector<int> lst;
  for (int i = 0, l, r, p, q; i < n; ++i) {
    cin >> l >> r >> p >> q;
    int tmp = p * inv(q) % mod;
    lst.push_back(tmp);
    const int tmp2 = (1 - tmp + mod) % mod;
    int b_i = tmp * inv(tmp2) % mod;
    if (r <= m) {
      seg[r].emplace_back(l, b_i);
    }
  }
  int c = 1;
  for (const int a: lst) {
    (c *= (1 - a + mod) % mod) %= mod;
  }
  vector<int> dp(m + 1);
  dp[0] = 1;
  for (int i = 1; i <= m; ++i) {
    int ttl = 0;
    for (auto [l, b]: seg[i]) {
      ttl = (ttl + dp[l - 1] * b) % mod;
    }
    dp[i] = ttl % mod;
  }
  cout << (c * dp[m] % mod + mod) % mod << endl;
}

// #define CP_MULTI_TEST_CASES

signed main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int t = 1;
#ifdef CP_MULTI_TEST_CASES
  cin >> t;
#endif
  while (t--) {
    Main();
  }
  return cout << flush, fflush(stdout), 0;
}

代码解释

1. 输入处理：读取输入数据，包括线段数量 \( n \) 和单元格数量 \( m \)，以及每个线段的左右端点 \( l_i, r_i \) 和概率参数 \( p_i, q_i \)。
2. 概率计算：对每个线段，计算其存在概率 \( a_i = \frac{p_i}{q_i} \)（模 \( 998244353 \) 下的值）和变换后的值 \( b_i = \frac{a_i}{1 - a_i} \)。
3. 常数因子 \( C \)：计算所有线段都不存在的概率乘积 \( C = \prod_{i=1}^{n} (1 - a_i) \)。
4. 动态规划初始化：初始化 \( dp[0] = 1 \)（表示空区间的概率为1），\( dp[1..m] \) 初始为0。
5. 动态规划转移：遍历每个单元格 \( i \)（从1到 \( m \))，对于每个右端点为 \( i \) 的线段，更新 \( dp[i] \) 为 \( dp[l_k - 1] \times b_k \) 的累加和。
6. 结果计算：最终概率为 \( C \times dp[m] \)，输出结果模 \( 998244353 \).

该算法高效地利用动态规划和预处理，在 \( O(n + m) \) 时间内解决问题，适用于给定的约束条件。