题解：CF2125D Segments Covering

· · 题解

题意

给定若干区间，每个区间有概率存在或不存在，问区间覆盖 [1, m] 的概率。

分析

考虑 DP。

用 f_i 表示 [1,m] 被恰好覆盖一次的概率。利用区间进行转移，我们用一个 vector 记下，以每个位置为结尾的区间编号。那么

f_i = \sum_{j:r_j = i}{f_{l_j - 1} \cdot prd(i, j)}

其中 l_j, r_j 分别表示区间 j 的左右端点，prd(i,j) 表示 [l_j, r_j] 被区间 j 覆盖的概率，有

prd(i,j) = pr_j\prod_{k \neq j:r_k \in [l_j, r_j]}(1-pr_k)

其中 pr_j 为区间 j 存在的概率。我们可以预处理一个前缀乘积，即

prd_i = \prod_{k:r_k \le i}(1-pr_k)

于是

prd(i,j) = prd_i / prd_{l_j - 1} / (1 - pr_j) \cdot pr_j

可以快速转移。

代码

#include <bits/stdc++.h>
#define int long long
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define _rep(i, l, r) for (int i = (l); i >= (r); i--)

using namespace std;

constexpr int N = 2e5 + 10, P = 998244353;

inline int qpow(int a, int b) {
  int res = 1;
  for (; b; b >>= 1, a = a * a % P)
    if (b & 1) res = res * a % P;
  return res;
}
inline int inv(int a) {
  return qpow(a, P - 2);
}

int n, m;
struct Segment {
  int l, r, pr;
} seg[N];
vector<int> vec[N];
int f[N];
int prd[N];

signed main() {
  cin >> n >> m;
  fill(prd, prd + m + 1, 1);
  rep(i, 1, n) {
    cin >> seg[i].l >> seg[i].r;
    int p, q;
    cin >> p >> q;
    seg[i].pr = p * inv(q) % P;
    vec[seg[i].r].emplace_back(i);
    prd[seg[i].r] = prd[seg[i].r] * (1 - seg[i].pr + P) % P;
  }

  rep(i, 1, m) prd[i] = prd[i - 1] * prd[i] % P;

  f[0] = 1;
  rep(i, 1, m) {
    for (auto j : vec[i]) {
      const int &l = seg[j].l, &pr = seg[j].pr;
      int tmpPrd = prd[i] * inv(prd[l - 1]) % P * inv(1 - pr + P) % P * pr % P;
      f[i] = (f[i] + f[seg[j].l - 1] * tmpPrd % P) % P;
    }
  }
  cout << f[m] << "\n";

  return 0;
}