hubeikemi的个人博客
0%

位运算小技巧总结

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

逆推概率笔记

一、背景

  • 题目目标：计算多个区间随机出现时，每个格子恰好被一个区间覆盖的总概率。
  • 简化版本：去掉取模、逆元，用浮点数 p/q 表示区间出现概率。

二、核心流程

  1. 初始化 “都不出现” 的概率乘积（ans）

    • 每条区间不出现概率 = (q - p)/q
    • ans = ∏ (q - p)/q

  2. 动态规划 (DP)

    • 状态：dp[i] 表示从格子 1 到 i，在“都不出现”的前提下，恰好被覆盖一次的概率。
    • 初始：dp[0] = 1，dp[1..m] = 0

  3. 区间排序与转移

    • 先按 l、r 排序区间。

    • 对第 i 条区间 [l, r] 做：

      1
      dp[r] += dp[l - 1] * (p / (q - p));

  4. 结果计算

    • 最终答案 = ans * dp[m]

三、关键疑问与解答

问题1：为什么要除以 (q - p)？

  • 直觉误区：在“不出现”情况下，出现概率似乎为 0。
  • 条件概率：反向推导就是在“不出现”的条件下，推导“出现”的修正因子。
  • 公式推导：
    $P(出现|不出现) = \frac{P(出现)}{P(不出现)} = \frac{(p/q)}{((q-p)/q)} = \frac{p}{q - p}.$

问题2：什么是“反向推导”？

  • 指在“都不出现”的概率空间中，逆向演算某条区间突然出现对最终结果的影响。
  • 作用：给 dp 转移添加正确的概率修正因子。

四、小例子演示

  • m = 3, 区间 A:[1,2], p/q=1/2; B:[3,3], p/q=1/3
  • ans = (1/2)*(2/3) = 1/3

  • DP 转移：

    1. A: dp[2] += dp[0] * (1/(2-1)) = 1 ⇒ dp[2] = 1
    2. B: dp[3] += dp[2] * (1/(3-1)) = 1/2 ⇒ dp[3] = 0.5
  • 最终：ans * dp[3] = 1/3 * 1/2 = 1/6

五、简化版代码（去模版、取模、快速幂）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
    double l, r, p, q;
};

bool cmp(Node a, Node b) {
    if (a.l == b.l) return a.r < b.r;
    return a.l < b.l;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<Node> seg(n);
    double ans = 1.0;

    for (int i = 0; i < n; ++i) {
        cin >> seg[i].l >> seg[i].r >> seg[i].p >> seg[i].q;
        ans *= (seg[i].q - seg[i].p) / seg[i].q;
    }

    sort(seg.begin(), seg.end(), cmp);
    vector<double> dp(m + 5, 0);
    dp[0] = 1.0;

    for (int i = 0; i < n; ++i) {
        dp[(int)seg[i].r] += dp[(int)seg[i].l - 1] * seg[i].p / (seg[i].q - seg[i].p);
    }

    cout << ans * dp[m] << endl;
    return 0;
}

备注：以上笔记可帮助队友快速理解“为什么除以 (q-p)”及反向推导思路。

六、示意图解

1
2
3
4
5
6
7
8
9
10
11
12
起点 dp[0] = 1.0
  |
  +-- 区间 A [1,2]
       p/q = 1/2，不出现概率 (q-p)/q=1/2
       修正因子 p/(q-p)=1/(2-1)=1
       => dp[2] += dp[0] * 1 = 1.0
             |
             +-- 区间 B [3,3]
                  p/q = 1/3，不出现概率 (q-p)/q=2/3
                  修正因子 p/(q-p)=1/(3-1)=1/2
                  => dp[3] += dp[2] * 1/2 = 0.5
最终答案 = ans * dp[3] = (1/2*2/3) * 0.5 = 1/6