概率論

APIO 2024 講課內(nèi)容

基礎(chǔ)

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

離散型隨機(jī)變量

AGC060C Large Heap

考慮轉(zhuǎn)化為二叉外向樹(shù)拓?fù)湫颉?/p>

\(u\) 點(diǎn)就是 \(A\) 層最左邊的點(diǎn)，\(v\) 是 \(B\) 層最右邊的點(diǎn)。所以我們只關(guān)心兩條鏈上選取方式，將兩條鏈提取出來(lái)，其他點(diǎn)看成兩條鏈上掛著的子樹(shù)。其實(shí)我們并不關(guān)心子樹(shù)具體怎么走，因?yàn)檫@對(duì)于鏈上的選取順序無(wú)影響，所以只需要記錄鏈取到了哪里。

但是子樹(shù)大小是有影響的，因?yàn)槲覀兪窃谒泻戏ǖ呐帕兄羞x擇，那么你子樹(shù)大小越大，你的拓?fù)湫蚓陀懈蟮母怕试诟懊妫@個(gè)概率與子樹(shù)大小呈線性。于是你從鏈?zhǔn)酵七M(jìn)的時(shí)候，到底是推進(jìn)左鏈還是右鏈，是要乘以一個(gè)概率的。按照兩邊子樹(shù)大小來(lái)分配概率。

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

CF1096E The Top Scorer

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

ARC150D Removing Gacha

和后文的 CF280C Game on Tree 是雙倍經(jīng)驗(yàn)，這里就不講了。

ABC270Ex add 1

很有意思的題目！本題的難點(diǎn)是狀態(tài)量很大的題目如何高效刻畫(huà)。

觀察到大部分的變換都比較對(duì)稱(chēng)，因此猜測(cè)可以有一個(gè)統(tǒng)一的變量來(lái)刻畫(huà)。

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

發(fā)現(xiàn)可以直接將狀態(tài) \(\{c_1,c_2\dots c_n\}\) 簡(jiǎn)化為 \(\max\{a_i-c_i\}\) ！我們并不需要記錄局部狀態(tài)是因?yàn)樵谥挥腥?\(c_i\gets c_i+1\) 的時(shí)候，可以只記錄上述狀態(tài)，加入單點(diǎn) \(c_i\gets 0\) 之后，只會(huì)讓 \(a_i-c_i\) 變大，我們只需要讓這個(gè)唯一改變的 \(a_i-c_i\) 和之前的最大值 chkmax 就行了。如果出現(xiàn)單點(diǎn) \(a_i-c_i\) 變小，就不能這么記錄了，因?yàn)槲覀兛赡軙?huì)讓最大值減小，無(wú)法判斷誰(shuí)是新的最大值了。

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

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

連續(xù)型隨機(jī)變量

ARC113F Social Distance

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

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

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

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

通過(guò)前綴和優(yōu)化做到時(shí)間復(fù)雜度 \(O(n^3)\)。

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

進(jìn)行 DP，可以得到 \(f_{i,j}\) 是一個(gè)關(guān)于 \(x\) 的 \(O(n)\) 次多項(xiàng)式，我們維護(hù)這個(gè)多項(xiàng)式的系數(shù)，每次轉(zhuǎn)移是一個(gè)多項(xiàng)式乘以直線的形式，可以 \(O(n)\) 轉(zhuǎn)移，最后對(duì)于多項(xiàng)式進(jìn)行積分求答案即可。時(shí)間復(fù)雜度 \(O(n^6)\)。

高斯消元

狀態(tài)圖是不是 DAG，導(dǎo)致各個(gè)狀態(tài)之間有牽連，可以采用高斯消元。暴力高斯消元是 \(O(n^3)\) 的，但是由于一些特殊性質(zhì)有的時(shí)候我們可以?xún)?yōu)化到 \(O(n^2)\)。

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

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

P4457 [BJOI2018] 治療之雨

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

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

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

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

隨機(jī)游走

• 根據(jù)需求來(lái)設(shè)未知數(shù)。比如可以設(shè)期望經(jīng)過(guò)次數(shù)或者到達(dá)終點(diǎn)的期望步數(shù)。

假設(shè)目標(biāo)是 \(s\to t\)，我們?cè)O(shè) \(f_u\) 表示從 \(u\) 點(diǎn)第一次到達(dá) \(t\) 所需要的期望步數(shù)。于是 \(f_u=1+\dfrac{1}{deg_u}\sum f_v\)。其中 \(f_t=0\)。

CF24D Broken robot

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

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

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

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

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

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

然后可以發(fā)現(xiàn)這些式子行間無(wú)后效性，行內(nèi)有后效性。

于是暴力就是從倒數(shù)第二行開(kāi)始倒著高斯消元，每一行都對(duì)于行內(nèi) \(n\) 個(gè)格子做一次高斯消元。時(shí)間復(fù)雜度 \(O(nm^3)\)。

觀察系數(shù)矩陣可以發(fā)現(xiàn)只有對(duì)角線以及對(duì)角線的周?chē)母褡佑兄怠?br> 于是我們可以采取以下策略消元，對(duì)于第 \(i\) 行，應(yīng)該是 \(i-1,i,i+1\) 三個(gè)位置有值，在第 \(i\) 行之前我們要消掉 \(i-1\)。從第 \(i\) 行起我們先把 \(a_{i,i}\) 系數(shù)變?yōu)?\(1\)。然后把第 \(i+1\) 行的 \(a_{i+1,i}\) 消掉。然后對(duì)于 \(a_{i,i+1}\) 的處理，我們可以一直消到最后一行，然后倒著回去帶入，把 \(a_{i,i+1}\) 處理掉。時(shí)間復(fù)雜度 \(O(nm)\)。

P3232 [HNOI2013] 游走

發(fā)現(xiàn)邊的量級(jí)很大，考慮轉(zhuǎn)化到點(diǎn)上去求解，再推邊的相關(guān)期望。

設(shè) \(f_u\) 表示 \(u\) 點(diǎn)的期望經(jīng)過(guò)次數(shù)。

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

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

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

幾個(gè)細(xì)節(jié)，就是 \(1\) 點(diǎn)初始有一次經(jīng)過(guò)，還有就是 \(n\) 點(diǎn)進(jìn)去了不能出去。

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

對(duì)于邊排序之后分配編號(hào)即可。

補(bǔ)充

重要公式

• 第一個(gè)公式非常重要，如果遇到總權(quán)值的期望就嘗試拆開(kāi)成每個(gè)權(quán)值期望累和。

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

\(E(xy)=E(x) \times E(y)\) 這個(gè)需要滿(mǎn)足獨(dú)立才成立。

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

注意事項(xiàng)

注意邊界情況特判！！！

CF1187F Expected Square Beauty

注意事件獨(dú)立性，\(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}])\)

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

\(\lvert i-j\rvert>1\) 為 \(p_i \times p_j\)，因?yàn)閮晌换ゲ挥绊憽?/p>

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

#6513. 「雅禮集訓(xùn) 2018 Day10」足球大戰(zhàn)

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

P4316 綠豆蛙的歸宿

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

如果是順推，設(shè) \(f_u\) 表示起點(diǎn)到 \(u\) 的期望長(zhǎng)度（？其實(shí)很怪，這題并不是要求到 \(u\) 的期望長(zhǎng)度，因?yàn)榭赡艿讲涣?\(u\) 哪里來(lái)的期望長(zhǎng)度。所以感覺(jué)設(shè)計(jì)出來(lái)的終態(tài)必須要是可以 100% 到達(dá)的，終點(diǎn)雖然不唯一但是 100% 能到達(dá)終點(diǎn)）。轉(zhuǎn)移 \(v \to u\) 的時(shí)候 \(f_v\) 要乘上當(dāng)前概率 \(deg_v\)，而路徑長(zhǎng)度還要乘上 \(deg_v \times p_v\)。

雜題

CF280C Game on Tree

期望線性性的應(yīng)用。將整體操作次數(shù)的期望轉(zhuǎn)到每個(gè)點(diǎn)被操作次數(shù)的期望。

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

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

CF464D World of Darkraft - 2

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

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

直接轉(zhuǎn)移是 \(O(n^2)\) 的，但是我們發(fā)現(xiàn)這題不需要什么逆元取模，而是直接輸出小數(shù)。可以利用這個(gè)特性，算一下一個(gè)物品從 \(x \to x+1\) 的期望次數(shù)是 \(k(x+1)\)。那么從 \(1 \to x\) 的期望次數(shù)就是累和，再令這個(gè)式子 \(\le n\)，發(fā)現(xiàn)期望升級(jí)次數(shù)在 \(500\) 左右，往后越大概率越小，小數(shù)點(diǎn)無(wú)法表示，所以我們可以取上界 \(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)\) （應(yīng)用：數(shù)學(xué)期望）
CF1523E Crypto Lights 這里的 \(suf(i)\) 表示一個(gè)概率，這樣就完成了期望到概率的轉(zhuǎn)化。注意本題還有概率經(jīng)典誤區(qū)：就是說(shuō)題面顯然不是說(shuō)把所有方案以等概率加起來(lái)，而是在決策中一步有其概率。也就是說(shuō)，某個(gè)進(jìn)行 \(i\) 后停止的狀態(tài)發(fā)生概率為 \(n\) 的 \(i\) 次下降冪分之一。

AGC030D Inversion Sum

首先，很妙的一步就是把總權(quán)值轉(zhuǎn)化為期望 \(\times\) 總的可能數(shù)。

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

發(fā)現(xiàn)全局逆序?qū)?shù)不好快速多次求解，發(fā)現(xiàn) \(n\) 范圍較小，于是我們可以回到逆序?qū)ψ罨镜亩x用 \((i,j)\) 產(chǎn)生貢獻(xiàn)。

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

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

P12251 [科大國(guó)創(chuàng)杯初中組 2025] 抽卡

ZROI2886. Slot machine