Moe's CF Life

Appearance

D. Segments Covering - 题解 ​

比赛与标签 ​

比赛: Educational Codeforces Round 181 (Rated for Div. 2) 标签: dp, math, probabilities 难度: 未提供喵~

主人，这是什么任务喵？ ​

哈喵~！各位算法大师们好呀，咱是乃们的专属解题猫娘！今天我们要征服的，是一道关于概率和动态规划的有趣问题哦！

是这样的说：我们有一条长长的、被分成 m 个格子的带子，格子从 1 到 m 编号。然后呢，有 n 条线段，每一条线段 i 都有它自己的管辖范围 [li, ri]，但它不是一定会粗线的哦！它出现的概率是 pi / qi。所有线段是否出现都是独立的事件呐。

我们的任务就是，计算出一种奇迹发生的概率：那就是每一个格子，从 1 到 m，都恰好被一条出现的线段覆盖。不能有任何一个格子被冷落，也不能有任何一个格子被两条或更多的线段覆盖，要求很严格的喵！

最后，我们要把这个概率对 998244353 取模后输出。准备好了吗？让我们一起开动脑筋吧！

来和咱一起分析吧，喵~ ​

一看到这种“恰好”和“概率”的问题，是不是感觉有点头大呀？直接去算所有可能的情况，那组合起来简直是天文数字！但是不要怕，让咱来带你理清思路，喵~

概率公式的华丽变身！ ​

首先，我们要求的事件是“所有格子都被恰好一个线段覆盖”。这等价于：我们选择一个线段的子集 S，这些线段 S 必须满足两个条件：

  1. 它们的并集恰好是 [1, m]。
  2. 它们两两之间没有交集。 换句话说，集合 S 里的线段们必须能完美地拼接成 [1, m] 这个大区间，我们称这样的 S 为一个“有效划分”。

对于一个特定的有效划分 S，它发生的概率是多少呢？ 因为所有线段出现与否是独立的，所以这个概率是： P(S) = ( Π_{i ∈ S} P_i ) * ( Π_{j ∉ S} (1 - P_j) ) 这里 P_i 是线段 i 出现的概率，1 - P_j 是线段 j 不出现的概率。

我们的最终目标，就是把所有可能的有效划分 S 的概率加起来： Total_Prob = Σ_{S is a valid partition} P(S)

这个求和看起来还是很可怕，对吧？别急，看咱的变身魔法！我们把 P(S) 的公式稍微变形一下： P(S) = ( Π_{i ∈ S} P_i ) * ( (Π_{k=1 to n} (1 - P_k)) / (Π_{i ∈ S} (1 - P_i)) ) 整理一下，把和 S 有关的项放在一起： P(S) = ( Π_{k=1 to n} (1 - P_k) ) * ( Π_{i ∈ S} (P_i / (1 - P_i)) )

看呐！这个公式被我们拆成了两部分：

  1. P_total = Π_{k=1 to n} (1 - P_k)：这部分是所有线段都不出现的概率，它对于任何一个有效划分 S 都是一个公共的乘积因子！我们可以先把它算出来。
  2. W(S) = Π_{i ∈ S} (P_i / (1 - P_i))：我们把 P_i / (1 - P_i) 定义为每条线段 i 的“权重” w_i。那么 W(S) 就是划分 S 中所有线段的权重之积。

于是，我们要求的总概率就变成了： Total_Prob = P_total * ( Σ_{S is a valid partition} W(S) )

现在问题就转化成：计算所有有效划分的权重之和！这个问题是不是看起来熟悉多了？这简直是为动态规划量身定做的嘛，喵！

DP 出击！ ​

我们可以定义一个 DP 数组： dp[i] = 完美覆盖区间 [1, i] 的所有有效划分的权重之和。

状态定义: dp[i] 表示将 [1, i] 区间完美划分的权重总和。 基本情况 (Base Case): dp[0] = 1。这代表一个空区间 [1, 0] 只有一个划分方式（就是不选任何线段），其权重是 1（空乘积为 1）。这个定义对于后续的递推至关重要哦！ 状态转移: 我们怎么计算 dp[i] 呢？ 要划分 [1, i]，我们可以考虑覆盖 i 的最后一条线段。假设这条线段是 [l, i]（我们称它为线段 k）。 如果 [l, i] 是划分的最后一部分，那么 [1, l-1] 这部分也必须被完美划分。而 [1, l-1] 的所有划分方式的权重之和，正好就是 dp[l-1]！ 所以，对于一个以 [l, i] 结尾的划分，它的权重之和就是 dp[l-1] * w_k。

dp[i] 就是所有可能作为结尾的线段 [l, i] 贡献的权重之和。 dp[i] = Σ_{所有以 i 为右端点的线段 k=[lk, i]} (dp[lk - 1] * w_k)

最终答案: 我们最终想要的，就是覆盖整个 [1, m] 区间的权重和，也就是 dp[m]。 最后，别忘了乘上我们之前算好的 P_total！ 最终概率 = dp[m] * P_total。

为了高效地找到所有以 i 为右端点的线段，我们可以预处理一下，用一个邻接表 segs_by_r 把所有线段按照它们的右端点 r 分组。这样，在计算 dp[i] 时，我们只需要遍历 segs_by_r[i] 里的线段就可以啦，非常高效！

代码实现喵！ ​

下面就是把我们的思路变成代码的时刻啦！咱已经给代码加上了详细的注释，方便主人理解每一行都在做什么哦~

cpp
#include <iostream>
#include <vector>
#include <numeric>

// Using GNU G++23 14.2 (64 bit, msys2)
// which supports C++23 standard.

// 定义模数，是只可爱的质数喵~
constexpr long long MOD = 998244353;

// 快速幂函数，用来计算 a^b % MOD，求逆元的时候会用到！
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 利用费马小定理计算模逆元，(n / m) % MOD = (n * m^(MOD-2)) % MOD
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

int main() {
    // 加速输入输出，让程序跑得飞快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    int m;
    std::cin >> n >> m;

    // P_total 是所有线段都不出现的概率，我们先算好这个公共因子
    long long P_total = 1;

    // 用一个邻接表结构，按右端点 r 存储线段
    // 每个元素是 {左端点 l, 权重 w}
    std::vector<std::vector<std::pair<int, long long>>> segs_by_r(m + 1);

    for (int i = 0; i < n; ++i) {
        int l, r;
        long long p, q;
        std::cin >> l >> r >> p >> q;

        // 线段 i 不出现的概率: 1 - P_i = 1 - p/q = (q-p)/q
        long long prob_not_exists = ((q - p) * modInverse(q)) % MOD;
        
        // 线段 i 的权重: w_i = P_i / (1 - P_i)
        // w_i = (p/q) / ((q-p)/q) = p / (q-p)
        long long w = (p * modInverse(q - p)) % MOD;
        
        // 把线段信息存入对应右端点的桶里
        segs_by_r[r].push_back({l, w});
        
        // 更新 P_total，累乘上每条线段不出现的概率
        P_total = (P_total * prob_not_exists) % MOD;
    }

    // dp[i] 将存储区间 [1, i] 的所有有效划分的权重之和
    std::vector<long long> dp(m + 1, 0);
    // Base Case: 空区间的划分权重和为 1
    dp[0] = 1; 

    // 开始 DP 啦！从 1 到 m 填充 dp 数组
    for (int i = 1; i <= m; ++i) {
        // 状态转移方程: dp[i] = Σ dp[l_k - 1] * w_k
        // 我们遍历所有以 i 为右端点的线段 k
        for (const auto& seg : segs_by_r[i]) {
            int l = seg.first;
            long long w = seg.second;
            // 累加由线段 [l, i] 构成的划分的权重
            dp[i] = (dp[i] + dp[l - 1] * w) % MOD;
        }
    }

    // [1, m] 的总权重和就是 dp[m]
    long long sum_of_weights = dp[m];
    
    // 最终概率 = 总权重和 * 公共概率因子
    long long final_prob = (sum_of_weights * P_total) % MOD;

    std::cout << final_prob << std::endl;

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(n log MOD + m) 的说。

    • 预处理阶段，我们遍历 n 条线段，每条线段计算一次模逆元，需要 O(log MOD) 的时间。所以这部分是 O(n log MOD)。
    • DP 阶段，我们有一个从 1 到 m 的循环。在循环内部，我们遍历以 i 为右端点的线段。由于每条线段只会被它自己的右端点处理一次，所以所有内层循环的总迭代次数就是 n。因此，DP 部分的总复杂度是 O(n + m)。
    • 两者相加，总时间复杂度就是 O(n log MOD + m)。因为 log MOD 是个常数，所以也可以看作 O(n + m)，非常快喵！

  • 空间复杂度: O(n + m) 的说。

    • segs_by_r 存储了 n 条线段的信息，需要 O(n) 空间。
    • dp 数组的大小是 m+1，需要 O(m) 空间。
    • 所以总空间复杂度是 O(n + m)。

知识点与总结 ​

这次探险我们又学会了好多东西呐，快拿小本本记下来！

  1. 概率问题转化: 这是本题最核心的技巧！通过对概率公式进行代数变形，我们成功地将一个复杂的概率求和问题，转化为了一个“权重和”的组合计数问题。P(S) = P_total * W(S) 这一步是解题的关键，一定要记住这个思路，以后碰到类似的独立概率问题可以尝试一下！

  2. 动态规划 (DP): 经典的区间DP模型。dp[i] 的定义清晰地抓住了问题的子结构，而状态转移则完美地利用了“最后一段”的思想来构建更大的解。

  3. 优化DP转移: 通过 segs_by_r 预处理，我们将 DP 转移的复杂度从 O(i) 或 O(n) 优化到了均摊 O(1)（每条线段只贡献一次计算），这是处理区间类 DP 的常用优化手段。

  4. 模运算: 在算法竞赛中，处理大数和概率问题时，模运算是家常便饭。熟练掌握快速幂和费马小定理求逆元是必备技能哦！

总之，这是一道将数学洞察力与经典DP模型巧妙结合的好题。只要我们能勇敢地推导公式，发现其中的奥秘，问题就会迎刃而解啦！希望这次的讲解对你有帮助，下次再一起挑战更有趣的问题吧，喵~！

Released under the MIT License.

Copyright © 2024-present Moe