概率論

APIO 2024 講課內容

基礎

樣本空間：隨機實驗的所有結果構成集合 \(\Omega\)。
\(e.g.\) 拋硬幣 \(\Omega=\{H,T\}\)，拋 \(n\) 次就是 \(\{H,T\}^n\)。
事件：是 \(\Omega\) 的子集。
概率空間：為 \(\Omega\) 中的每個元素賦予一個發生的概率，用 \(P: \Omega \to [0,1]\) 表示。所有元素概率之和為 \(1\)。那么，\(P(A)=\sum\limits_{a \in A}P(a)\)。
隨機變量：\(X\) 從一個概率空間中抽取，以 \(P(a)\) 的概率取值為 \(a\)。
期望：\(E(x)=\sum P(X=a)a\)。
離散型隨機變量：只有有限個 \(a\) 滿足 \(P(X=a)>0\) 的情況。
連續型隨機變量：無限個 \(a\)，滿足 \(P(X=a)>0\)。
條件概率：\(P(A|B)\) 定義為在 \(B\) 發生的條件下，\(A\) 發生的概率。畫個圖理解就是概率空間內，\(A\) 與 \(B\) 的面積并占 \(B\) 面積的百分比，也就是 \(P(A|B)=\frac{P(AB)}{P(B)}\)。
貝葉斯公式：\(P(A|B)=\frac{P(B|A)P(A)}{P(B)}\)，應用就是交換條件概率中的 \(A\) 和 \(B\)。

離散型隨機變量

AGC060C Large Heap

考慮轉化為二叉外向樹拓撲序。

\(u\) 點就是 \(A\) 層最左邊的點，\(v\) 是 \(B\) 層最右邊的點。所以我們只關心兩條鏈上選取方式，將兩條鏈提取出來，其他點看成兩條鏈上掛著的子樹。其實我們并不關心子樹具體怎么走，因為這對于鏈上的選取順序無影響，所以只需要記錄鏈取到了哪里。

但是子樹大小是有影響的，因為我們是在所有合法的排列中選擇，那么你子樹大小越大，你的拓撲序就有更大的概率在更前面，這個概率與子樹大小呈線性。于是你從鏈式推進的時候，到底是推進左鏈還是右鏈，是要乘以一個概率的。按照兩邊子樹大小來分配概率。

設 \(f_{i,j}\) 表示左邊選取了 \(i\) 個點，右邊選取了 \(j\) 個點的方案數，使用刷表法來轉移，對于所有不合法的 \(i,j\) （不滿足 \(P_U<P_V\) 的）我們直接在 DP 遇到的時候將 \(f\) 值設為 \(0\) 即可。時間復雜度 \(O(n^2)\)。

CF1096E The Top Scorer

簡單題。先要枚舉 \(a_1\) 得分，然后得分相同的時候，是等概率一個人獲勝，這個不好直接處理，所以我們必須枚舉同分人數。最后直接計算一個 \(\sum x_i=C\)，\(x_i\in [0,LIM]\) 的方案數，下界直接平移 \(1\) 就處理掉了，上界可以直接使用容斥，欽定若干不滿足條件然后用組合數計算方程解的個數即可。

ARC150D Removing Gacha

和后文的 CF280C Game on Tree 是雙倍經驗，這里就不講了。

ABC270Ex add 1

很有意思的題目！本題的難點是狀態量很大的題目如何高效刻畫。

觀察到大部分的變換都比較對稱，因此猜測可以有一個統一的變量來刻畫。

令計數器數值為 \(c_i\)，原本需要記錄的狀態是 \(\{c_1,c_2\dots c_n\}\)，目標狀態是 \(\forall i,c_i\ge a_i\)，有如下變換全局 \(c_i\gets c_i+1\) 和 單點 \(c_i\gets 0\)。

發現可以直接將狀態 \(\{c_1,c_2\dots c_n\}\) 簡化為 \(\max\{a_i-c_i\}\) ！我們并不需要記錄局部狀態是因為在只有全局 \(c_i\gets c_i+1\) 的時候，可以只記錄上述狀態，加入單點 \(c_i\gets 0\) 之后，只會讓 \(a_i-c_i\) 變大，我們只需要讓這個唯一改變的 \(a_i-c_i\) 和之前的最大值 chkmax 就行了。如果出現單點 \(a_i-c_i\) 變小，就不能這么記錄了，因為我們可能會讓最大值減小，無法判斷誰是新的最大值了。

然后就很好做了，按照經典期望逆推，我們設 \(f_x\) 當前 \(\max\{a_i-c_i\}=x\) 的時候期望還有多少次可以達到終點 \(f_0\)。我們要求的就是 \(f_0\)，且已知 \(f_{a_n}=0\)。假如某次我們選擇了 \(y\)，那么 \(x\) 的變化是 \(x\gets \max(a_y,x-1)\)，根據這個可以輕松列出期望方程。假設 \(x\in (a_y,a_{y+1}]\)，那么有

將這個式子改寫為 \(f_{x}\to f_{x-1}\) 的形式，就可以從 \(f_{a_n}\) 推到 \(f_0\) 了。在每一個 \((a_i,a_{i+1}]\) 段中用矩陣優化即可。

連續型隨機變量

ARC113F Social Distance

連續型的求期望太難，考慮設 \(f(x)\) 表達答案 \(\ge x\) 的概率，最后答案就是 \(\int f(x)dx\)。

令 \(p_i-p_{i-1}\ge x\)，同時 \(p_i\in [l_i,r_i]\)，這個約束是一個滑動區間不好處理。令 \(q_i\gets p_i-ix\) 就很好處理了。\(q_i\in [l_i-ix,r_i-ix]\) 均勻隨機分布，求 \(q_i\) 遞增概率。

這個問題的離散版本就是 P3643 [APIO2016] 劃艇，本題不僅是實數域，而且還要求對于連續的 \(x\) 算出不同 \(x\) 之下問題的答案。

先解決實數域這個問題，將點離散化之后得到 \(\{y_i\}\)。設 \(f_{i,j}\) 表示考慮到了前 \(i\) 個元素，其屬于區間 \([y_j,y_{j+1})\)，且這些點都有序的概率。

通過前綴和優化做到時間復雜度 \(O(n^3)\)。

現在要處理第二個問題，如何對于連續的 \(x\) 的求解。首先 DP 方程對于 \([l'_i,r'_i]\) 是有約束的，要求 \([l'_i,r'_i]\) 包含其落在的區間。因此對于 \(O(n^2)\) 組 \([l_i-ix,r_i-x]\) 和 \([l_j-jx,r_j-jx]\) 兩兩求交點，可以得到 \(O(n^2)\) 組臨界點，得到 \(O(n^2)\) 個區間，單個區間內包含關系不變。

進行 DP，可以得到 \(f_{i,j}\) 是一個關于 \(x\) 的 \(O(n)\) 次多項式，我們維護這個多項式的系數，每次轉移是一個多項式乘以直線的形式，可以 \(O(n)\) 轉移，最后對于多項式進行積分求答案即可。時間復雜度 \(O(n^6)\)。

高斯消元

狀態圖是不是 DAG，導致各個狀態之間有牽連，可以采用高斯消元。暴力高斯消元是 \(O(n^3)\) 的，但是由于一些特殊性質有的時候我們可以優化到 \(O(n^2)\)。

有的矩陣都很稀疏，可以每次只對于 \(O(1)\) 個位置有值的位置進行消元，復雜度就是 \(O(n^2)\) 的。

如果矩陣很密集的話，有的時候每個變量都比較對稱，因此有一些規律可以使用，之后例題中 Slot machine 中 \(k=1\) 的部分分就是這樣子的，也可以做到 \(O(n^2)\)。

P4457 [BJOI2018] 治療之雨

設 \(P_i\) 表示在降血過程中降 \(i\) 滴血的概率。于是有

然后就可以列期望的方程了，注意特判 \(E_n\)，

利用高斯消元可以 \(O(n^3)\) 暴力解。

觀察一些增廣矩陣，發現對于第 \(i\) 行，只有 \([1,i+1]\) 的位置有值。還是類似高斯消元的步驟。我們在消第 \(i\) 行的時候 \([1,i-1]\) 的列都為 \(0\)，此時只有 \(i\) 和 \(i+1\) 列是有值的。按照常理我們往下消的時候應該對于后面每一行都減去 \([i,n+1]\) 的系數，但是由于后面一堆非 \(0\) 位置。所以我們只需要消去 \(i,i+1,n+1\) 三個位置的值即可。這樣子消元部分的復雜度為 \(O(n^2)\)，總的時間復雜度是 \(O(Tn^2)\)。

隨機游走

• 根據需求來設未知數。比如可以設期望經過次數或者到達終點的期望步數。

假設目標是 \(s\to t\)，我們設 \(f_u\) 表示從 \(u\) 點第一次到達 \(t\) 所需要的期望步數。于是 \(f_u=1+\dfrac{1}{deg_u}\sum f_v\)。其中 \(f_t=0\)。

CF24D Broken robot

對于邊界位置情況特判一下（可能不能往左/右走了），其他情況就是按照上述通法列式子即可。設 \(f_{i,j}\) 表示從格子 \((i,j)\) 走到終點的期望步數。

對于第 \(1\) 列，\(f_{i,1}=\frac13(f_{i,1}+f_{i,2}+f_{i+1,1})+1\)。

對于第 \(m\) 列，\(f_{i,m}=\frac13(f_{i,m}+f_{i,m-1}+f_{i+1,m})+1\)。

對于第 \(2-m\) 列，\(f_{i,j}=\frac14(f_{i,j}+f_{i,j-1}+f_{i,j+1}+f_{i+1,j})+1\)。

同時特判 \(m=1\)。

整理一下可以得到增廣矩陣。

然后可以發現這些式子行間無后效性，行內有后效性。

于是暴力就是從倒數第二行開始倒著高斯消元，每一行都對于行內 \(n\) 個格子做一次高斯消元。時間復雜度 \(O(nm^3)\)。

觀察系數矩陣可以發現只有對角線以及對角線的周圍的格子有值。
于是我們可以采取以下策略消元，對于第 \(i\) 行，應該是 \(i-1,i,i+1\) 三個位置有值，在第 \(i\) 行之前我們要消掉 \(i-1\)。從第 \(i\) 行起我們先把 \(a_{i,i}\) 系數變為 \(1\)。然后把第 \(i+1\) 行的 \(a_{i+1,i}\) 消掉。然后對于 \(a_{i,i+1}\) 的處理，我們可以一直消到最后一行，然后倒著回去帶入，把 \(a_{i,i+1}\) 處理掉。時間復雜度 \(O(nm)\)。

P3232 [HNOI2013] 游走

發現邊的量級很大，考慮轉化到點上去求解，再推邊的相關期望。

設 \(f_u\) 表示 \(u\) 點的期望經過次數。

對于 \(u=1\),\(f_u=\sum\limits_{(u,v)~v\neq n} \dfrac{f_v}{d_v}+1\)

對于 \(2<u<n\)，\(f_u=\sum\limits_{(u,v)~v\neq n} \dfrac{f_v}{d_v}\)

對于 \(u=n\)，\(f_u=1\)

幾個細節，就是 \(1\) 點初始有一次經過，還有就是 \(n\) 點進去了不能出去。

對于每條邊 \((u,v)\) 的就是 \(\dfrac{f_u}{d_u}+\dfrac{f_v}{d_v}\)。

對于邊排序之后分配編號即可。

補充

重要公式

• 第一個公式非常重要，如果遇到總權值的期望就嘗試拆開成每個權值期望累和。

\(E(x+y)=E(x)+E(y)\) 該式子始終成立。

\(E(xy)=E(x) \times E(y)\) 這個需要滿足獨立才成立。

\(E(x^2)=E((x-1)^2)+2E(x-1)+1\) P1654 OSU!

注意事項

注意邊界情況特判！！！

CF1187F Expected Square Beauty

注意事件獨立性，\(E(B(x))=E(\sum\limits_{i=1}^{n-1}[x_i≠x_{i+1}])\)

\(E(B^2(x))=E(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[x_i≠x_{i-1}][x_j≠x_{j-1}])\)

分類討論：\(i=j\) 為 \(p_i\)

\(\lvert i-j\rvert>1\) 為 \(p_i \times p_j\)，因為兩位互不影響。

\(\lvert i-j\rvert =1\) 直接容斥 \(1-q_i-q_j+P(q_i \cup q_j)\)

#6513. 「雅禮集訓 2018 Day10」足球大戰

贏球概率為 \(p\)，在 \(n\) 場里面至少贏 \(i\) 場的概率是 \(C^i_n \times p^i\)，不是恰好 \(i\) 場的概率，注意還要乘上組合數（因為這里的概率是用計數然后作商算的，計數就需要不能漏）。概率算式可以自己舉簡單例子驗證正確性

P4316 綠豆蛙的歸宿

很重要的一題，遞推求期望要逆推。所以本題只能設 \(f_u\) 表示 \(u\) 到終點的期望路徑長度。

如果是順推，設 \(f_u\) 表示起點到 \(u\) 的期望長度（？其實很怪，這題并不是要求到 \(u\) 的期望長度，因為可能到不了 \(u\) 哪里來的期望長度。所以感覺設計出來的終態必須要是可以 100% 到達的，終點雖然不唯一但是 100% 能到達終點）。轉移 \(v \to u\) 的時候 \(f_v\) 要乘上當前概率 \(deg_v\)，而路徑長度還要乘上 \(deg_v \times p_v\)。

雜題

CF280C Game on Tree

期望線性性的應用。將整體操作次數的期望轉到每個點被操作次數的期望。

設 \(f_i\) 為 \(i\) 被操作的次數，\(p_i\) 為 \(i\) 被選中的概率，顯然有 \(f_i\in \{0,1\}\)。

\(p_i\) 的求解是一個經典的數學問題，考慮根到 \(i\) 這條祖孫鏈（顯然選其他點對于 \(i\) 是否被刪除無影響），只有在第一步就選 \(i\) 才能操作到 \(i\)，得到 \(p_i=\frac{1}{dep_i}\)，帶入求解即可。

CF464D World of Darkraft - 2

首先，明確一點就是只需要算出一個物品的期望然后 \(\times k\) 即可。

首先這題必須逆推否則要乘上一個概率，設 \(f_{i,j}\) 表示還剩 \(i\) 次抽卡機會的時候，目前最高等級為 \(j\) 可以期望獲得金錢數。

直接轉移是 \(O(n^2)\) 的，但是我們發現這題不需要什么逆元取模，而是直接輸出小數。可以利用這個特性，算一下一個物品從 \(x \to x+1\) 的期望次數是 \(k(x+1)\)。那么從 \(1 \to x\) 的期望次數就是累和，再令這個式子 \(\le n\)，發現期望升級次數在 \(500\) 左右，往后越大概率越小，小數點無法表示，所以我們可以取上界 \(1000\) 即可。

CF1523E Crypto Lights

\(\sum\limits_{i=1}^np(i)*i=\sum\limits_{i=1}^n\sum\limits_{j=i}^np(j)=\sum\limits_{i=1}^nsuf(i)\) （應用：數學期望）
CF1523E Crypto Lights 這里的 \(suf(i)\) 表示一個概率，這樣就完成了期望到概率的轉化。注意本題還有概率經典誤區：就是說題面顯然不是說把所有方案以等概率加起來，而是在決策中一步有其概率。也就是說，某個進行 \(i\) 后停止的狀態發生概率為 \(n\) 的 \(i\) 次下降冪分之一。

AGC030D Inversion Sum

首先，很妙的一步就是把總權值轉化為期望 \(\times\) 總的可能數。

于是就變成了每次有 \(\frac{1}{2}\) 概率去交換，求最后逆序對數的期望。

發現全局逆序對數不好快速多次求解，發現 \(n\) 范圍較小，于是我們可以回到逆序對最基本的定義用 \((i,j)\) 產生貢獻。

設 \(f_{i,j}\) 表示目前為止序列中 \(a_i < a_j\) 的概率。

當我們交換 \((u,v)\) 的時候有，\(f_{u,i}=\dfrac{1}{2}(f_{u,i}+f_{v,i})\)（其余轉移同理）。

P12251 [科大國創杯初中組 2025] 抽卡

ZROI2886. Slot machine