Probability

DP phân phối

Có $n$ phép thử độc lập, cần xác suất của một sự kiện về kết quả gộp (số lần thành công, tổng điểm). Gọi $dp_i[j]$ là xác suất sau $i$ phép thử, đại lượng gộp bằng $j$. Phép thử thứ $i + 1$ chỉ phụ thuộc chính nó, nên

Chỉ cần một mảng, duyệt $j$ giảm dần để không dùng giá trị vừa cập nhật. Cuối cùng cộng $dp_n[j]$ trên các $j$ thỏa sự kiện.

Trong hình, mỗi cột là xác suất có đúng $j$ lần thành công. Mỗi phép thử tách mỗi cột thành hai phần: một phần ở lại, một phần dịch sang phải.

Ví dụĐa Số Tín Hiệu

Đề. $N \le 2999$ (lẻ) cảm biến độc lập, cảm biến $i$ cho tín hiệu dương với xác suất $p_i$. Tính xác suất số tín hiệu dương nhiều hơn số tín hiệu âm, sai số $10^{-9}$.

Lời giải. dp[j] là xác suất có đúng $j$ tín hiệu dương trong các cảm biến đã xét. Hết cảm biến, cộng dp[j] với $j > N/2$.

Bước 1: thêm một cảm biến. $j$ dương có được từ $j$ dương cũ và cảm biến này âm, hoặc $j - 1$ dương cũ và cảm biến này dương. Duyệt $j$ giảm dần để dp[j - 1] vẫn là giá trị cũ khi dùng, như cái túi một chiều. dp[0] xử lý riêng vì không có dp[-1].

for (ll j = i; j >= 1; j--) dp[j] = dp[j] * (1 - p) + dp[j - 1] * p;
dp[0] *= 1 - p;

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

const ll N = 3005;
ll n;
double dp[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    dp[0] = 1;
    for (ll i = 1; i <= n; i++) {
        double p;
        cin >> p;
        for (ll j = i; j >= 1; j--) dp[j] = dp[j] * (1 - p) + dp[j - 1] * p;
        dp[0] *= 1 - p;
    }
    double ans = 0;
    for (ll j = n / 2 + 1; j <= n; j++) ans += dp[j];
    cout << fixed << setprecision(12) << ans << '\n';
}

ChạyInput3
0.20 0.50 0.90

Output0.550000000000

$N^2 / 2 \approx 4{,}5 \cdot 10^6$ phép; double đủ chính xác cho $10^{-9}$. long double chính xác hơn nhưng phải trả giá:

double nhanh hơn long double khoảng 2,7 lần. Quy tắc: dùng double khi sai số đề cho là $10^{-6}$ đến $10^{-9}$; chỉ đổi sang long double khi kết quả sai thật.

Kỳ vọng của max

Với biến $X$ nhận giá trị nguyên không âm, $E[X] = \sum_{k \ge 1} P(X \ge k)$: mỗi giá trị $x$ được đếm đúng $x$ lần, ở $k = 1, \dots, x$.

Công thức hợp với giá trị lớn nhất, vì $P(\max \le k)$ dễ tính: mọi phép thử đều không vượt $k$, tức $(k/m)^n$ khi mỗi lần chọn đều trong $1..m$. Vậy:

Lũy thừa số thực tính bằng pow. Vì $(k-1)/m < 1$ nên không tràn, chỉ có thể rất nhỏ.

Biến chỉ báo

$E[X + Y] = E[X] + E[Y]$ luôn đúng, kể cả khi $X$ và $Y$ phụ thuộc nhau. Muốn tính kỳ vọng của một đại lượng đếm, viết nó thành tổng các biến chỉ báo $I_e$ (bằng 1 nếu sự kiện $e$ xảy ra, 0 nếu không). Khi đó $E[\sum I_e] = \sum P(e)$, và việc còn lại là chọn sự kiện $e$ sao cho $P(e)$ dễ tính.

Đại lượng không phải tổng đếm, như bình phương độ dài, có thể viết thành tổng các phần tăng: nối thêm một phần tử vào đoạn liên tiếp dài $l$ thì $l^2$ tăng $2l + 1$. Kỳ vọng phần tăng chỉ cần $E[l]$, mà $E[l]$ có công thức truy hồi đơn giản.

Ví dụCây Con Biến Mất

Đề. Cây $n \le 10^5$ đỉnh, gốc 1. Mỗi lượt chọn đều một đỉnh còn lại và xóa nó cùng cây con của nó. Tính kỳ vọng số lượt.

Lời giải. Số lượt bằng số đỉnh được chọn trực tiếp. Đỉnh $v$ được chọn trực tiếp khi nó được chọn trước mọi tổ tiên của nó. Xét $d_v$ đỉnh trên đường từ gốc tới $v$: mỗi đỉnh có khả năng như nhau là đỉnh đầu tiên bị chọn, nên xác suất là $1/d_v$. Tuyến tính kỳ vọng cho phép cộng xác suất từng đỉnh dù các sự kiện phụ thuộc nhau: đáp án $\sum 1/d_v$, không cần mô phỏng quá trình xóa.

Bước 1: BFS tính độ sâu. dep[1] = 1: độ sâu tính cả gốc, đúng là số đỉnh trên đường từ gốc. Cộng 1.0 / dep[u] khi lấy mỗi đỉnh ra.

while (!q.empty()) {
    ll u = q.front();
    q.pop();
    ans += 1.0 / dep[u];
    for (ll v : adj[u])
        if (!dep[v]) dep[v] = dep[u] + 1, q.push(v);
}

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

const ll N = 1e5 + 5;
ll n, dep[N];
vector<ll> adj[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    queue<ll> q;
    q.push(1);
    dep[1] = 1;
    double ans = 0;
    while (!q.empty()) {
        ll u = q.front();
        q.pop();
        ans += 1.0 / dep[u];
        for (ll v : adj[u])
            if (!dep[v]) dep[v] = dep[u] + 1, q.push(v);
    }
    cout << fixed << setprecision(12) << ans << '\n';
}

ChạyInput5
1 2
1 3
3 4
3 5

Output2.666666666667

$O(n)$.

Ví dụNhịp Thành Công

Đề. $n \le 10^5$ phép thử độc lập, phép thứ $i$ thành công với xác suất $p_i$. Điểm là tổng bình phương độ dài các đoạn thành công liên tiếp cực đại. Tính kỳ vọng điểm.

Lời giải. Bình phương không cộng tuyến tính được, nên tính phần tăng: một đoạn dài $l$ thêm một phép thành công thì điểm tăng $(l + 1)^2 - l^2 = 2l + 1$. Gọi $e$ là kỳ vọng độ dài đoạn thành công kết thúc tại phép thử trước. Phép $i$ thành công với xác suất $p_i$, nên kỳ vọng phần tăng là $p_i(2e + 1)$.

Bước 1: cộng trước, cập nhật sau. Phần tăng dùng $e$ cũ. Rồi $e \leftarrow (e + 1) p_i$: thành công thì đoạn dài thêm 1, thất bại thì về 0.

ans += p * (2 * e + 1);
e = (e + 1) * p;

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

ll n;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    double e = 0, ans = 0;
    for (ll i = 1; i <= n; i++) {
        double p;
        cin >> p;
        ans += p * (2 * e + 1);
        e = (e + 1) * p;
    }
    cout << fixed << setprecision(12) << ans << '\n';
}

ChạyInput4
1 0.5 0.5 0

Output4.000000000000

$O(n)$.

DP kỳ vọng

Gọi $E(s)$ là kỳ vọng số bước còn lại từ trạng thái $s$. Một bước tốn 1 rồi chuyển sang $s'$ với xác suất $P(s \to s')$:

Nếu có xác suất $q$ ở lại $s$, chuyển vế: $E(s)(1 - q) = 1 + \sum_{s' \ne s} P(s \to s') E(s')$, rồi chia cho $1 - q$. Thứ tự tính ngược với quá trình, thường theo một đại lượng chỉ giảm.

Để giảm số chiều, gom các phần tử giống nhau: trạng thái chỉ cần số lượng mỗi loại, không cần biết phần tử nào.

Ví dụBàn Ăn Ngẫu Nhiên

Đề. $N \le 300$ đĩa, đĩa $i$ có $a_i \in \{1, 2, 3\}$ miếng. Mỗi lượt chọn đều một đĩa, còn miếng thì ăn một miếng. Tính kỳ vọng số lượt tới khi hết.

Lời giải. Các đĩa cùng số miếng như nhau, nên trạng thái chỉ cần $(c_1, c_2, c_3)$: số đĩa còn 1, 2, 3 miếng. Với $s = c_1 + c_2 + c_3$, xác suất chọn đĩa rỗng là $(N - s)/N$; chuyển vế phần ở lại đó được

Bước 1: hai tầng. Mảng $301^3$ số double quá lớn, nhưng tầng $c_3$ chỉ dùng tầng $c_3 - 1$. cur[c1][c2] là tầng hiện tại, pre là tầng trước.

Bước 2: thứ tự tính trong một tầng. Duyệt $c_2$ rồi $c_1$ tăng dần: cur[c1 - 1][c2] và cur[c1 + 1][c2 - 1] đều đã tính, vì $c_1 + c_2$ hoặc $c_2$ nhỏ hơn.

double e = n;
if (c1) e += c1 * cur[c1 - 1][c2];
if (c2) e += c2 * cur[c1 + 1][c2 - 1];
if (c3) e += c3 * pre[c1][c2 + 1];
cur[c1][c2] = e / s;

Bước 3: sang tầng sau. memcpy chép cả tầng sang pre. Hai bảng $305^2$ số double, chưa tới 1,5 MB.

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

const ll N = 305;
ll n, cnt[4];
double pre[N][N], cur[N][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        cnt[a]++;
    }
    for (ll c3 = 0; c3 <= cnt[3]; c3++) {
        for (ll c2 = 0; c2 + c3 <= n; c2++)
            for (ll c1 = 0; c1 + c2 + c3 <= n; c1++) {
                ll s = c1 + c2 + c3;
                if (!s) {
                    cur[c1][c2] = 0;
                    continue;
                }
                double e = n;
                if (c1) e += c1 * cur[c1 - 1][c2];
                if (c2) e += c2 * cur[c1 + 1][c2 - 1];
                if (c3) e += c3 * pre[c1][c2 + 1];
                cur[c1][c2] = e / s;
            }
        memcpy(pre, cur, sizeof(cur));
    }
    cout << fixed << setprecision(12) << pre[cnt[1]][cnt[2]] << '\n';
}

ChạyInput2
1 2

Output4.500000000000

$O(N^3 / 6)$, khoảng $4{,}5 \cdot 10^6$ trạng thái.

Kỳ vọng modulo

Đề in “$X \cdot Y^{-1} \bmod p$” khi kỳ vọng là phân số $X/Y$. Mọi phép cộng, nhân, chia trong công thức đều làm được theo modulo: xác suất $a/100$ thành $a \cdot 100^{-1}$, phép chia thành nhân nghịch đảo bằng lũy thừa nhanh. Cứ suy ra công thức như với số thực, rồi tính theo modulo; không so sánh hay làm tròn giữa chừng.

Ví dụChuỗi Cổng Khởi Động Lại

Đề. $n \le 2 \cdot 10^5$ cổng; ở cổng $i$ thành công với xác suất $p_i/100$ thì sang cổng tiếp theo (hoặc kết thúc ở cổng $n$), thất bại thì quay về cổng 1. Mỗi ngày kiểm một cổng. In kỳ vọng số ngày theo modulo $998244353$.

Lời giải. Gọi $q_i = p_1 p_2 \cdots p_i$ (theo xác suất). Một lần chạy từ cổng 1 tới được cổng $i$ (và tốn thêm ngày thứ $i$) với xác suất $q_{i-1}$, nên kỳ vọng số ngày của một lần chạy là $1 + q_1 + \dots + q_{n-1}$. Mỗi lần chạy thành công với xác suất $q_n$, số lần chạy kỳ vọng là $1/q_n$. Đáp án $(1 + q_1 + \dots + q_{n-1}) / q_n$.

Bước 1: tích lũy. inv100 là nghịch đảo của 100, để $p_i / 100$ thành phép nhân theo mô-đun. num cộng $q_{i-1}$ trước rồi mới nhân $q$ với $p_i$; hết vòng num $= 1 + q_1 + \dots + q_{n-1}$ và q $= q_n$.

for (ll i = 1; i <= n; i++) {
    ll p;
    cin >> p;
    num = (num + q) % MOD;
    q = q * p % MOD * inv100 % MOD;
}
cout << num * power(q, MOD - 2) % MOD << '\n';

Phép chia là nhân với nghịch đảo của q. Mọi bước chỉ là cộng, nhân, chia, nên tính theo mô-đun đúng như với số thực.

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

const ll MOD = 998244353;
ll n;

ll power(ll a, ll b) {
    ll r = 1;
    a %= MOD;
    while (b) {
        if (b & 1) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ll inv100 = power(100, MOD - 2), q = 1, num = 0;
    for (ll i = 1; i <= n; i++) {
        ll p;
        cin >> p;
        num = (num + q) % MOD;
        q = q * p % MOD * inv100 % MOD;
    }
    cout << num * power(q, MOD - 2) % MOD << '\n';
}

ChạyInput3
100 50 100

Output5

$O(n + \log p)$.