鞅的停時(shí)定理

感覺學(xué)起來還挺簡(jiǎn)單的，就是有太靈活逆天的式子。

這里不放鞅的定義了，可以看 百度百科

這里指的是連續(xù)鞅。

停時(shí)定理：

若滿足一下三個(gè)條件之一：

則有：

其實(shí)對(duì)于這個(gè)用的不多，一般會(huì)用勢(shì)能形式，條件也一般都會(huì)滿足。

但也有用這個(gè)簡(jiǎn)單的。

勢(shì)能形式：

考慮對(duì)于每個(gè)狀態(tài) \(A_i\)，設(shè)終狀態(tài)為 \(A_{\gamma}\)，構(gòu)造勢(shì)能函數(shù) \(\phi\)，使其滿足 \(E\{\phi(A_{n+1}-A_n)\mid A_n...A_1\}=-1\)，并且 \(E(\phi(A_{\gamma}))\) 唯一確定。

然后就可一用 \(E(\phi(A_{\gamma}))-E(\phi(A_{begin}))\) 求期望步數(shù)。

其實(shí)有更嚴(yán)謹(jǐn)?shù)谋磉_(dá)，但卵用沒有。

困難的就是構(gòu)造勢(shì)能函數(shù)，給幾個(gè)例題：

CF1025G Company Acquisitions

你們模擬賽出這個(gè)防 AK 是吧

狀態(tài)顯然。

考慮一個(gè)局面，只和一個(gè)每個(gè)根的子樹個(gè)數(shù)有關(guān)，考慮依此構(gòu)造每個(gè)子樹的勢(shì) \(f(x)\)，表示子樹有 \(x\) 個(gè)節(jié)點(diǎn)的勢(shì)，整個(gè)狀態(tài)的勢(shì)就是 \(\phi=\sum f\)

考慮每次的轉(zhuǎn)移，我們可以直接考慮欽定兩個(gè)點(diǎn)，每個(gè)都有 \(\frac 12\) 的概率是另一個(gè)父親，設(shè)這兩個(gè)點(diǎn)分別為 \(x,y\)，有：

因?yàn)槲覀兿氲玫揭恍﹪?yán)格的關(guān)系，不妨將條件適當(dāng)嚴(yán)格化，并欽定常量 \(f(0)=0\)，則有：

然后就可以直接 \(O(n)\) 求每個(gè)了，發(fā)現(xiàn)其滿足條件，可以作差。

CF1349D Slime and Biscuits

和剛才那個(gè)很像，但是發(fā)現(xiàn)沒法欽定，只能直接枚舉和式。

直接考慮每個(gè)被選中的概率，可以有和式（太長(zhǎng)了我不放了，賣個(gè)萌能放過我嗎 QwQ）

考慮還是將條件嚴(yán)格化，直接去掉和式，對(duì)于第 \(i\) 項(xiàng)欽定其值是 \(-\frac xm\)，然后就有遞推式子了。

放個(gè)題解吧，要是覺得我講的太爛了可以去看 luogu

最后有一個(gè)好玩的題：P4548 [CTSC2006] 歌唱王國(guó)

這個(gè)就是用停時(shí)定義比勢(shì)能簡(jiǎn)單的例子。

有形象講法：

考慮在每次唱歌錢有一個(gè)賭徒初始有一個(gè)硬幣來按照酋長(zhǎng)名字順序依次賭唱 \(a_i\)，如果贏了獲得 \(n\) 倍硬幣并繼續(xù)賭，輸了全賠。

考慮最后一定是剩下一個(gè)人賭完了，每個(gè) \(border\) 都會(huì)有一個(gè)人還在，其他人都輸完了。

考慮公平游戲出入平衡，可以賭徒期望得錢數(shù) \(\sum l_i^n\)，\(l\) 是每個(gè) \(border\) 長(zhǎng)度（算原串），也就是期望輪數(shù)。

證明就是直接對(duì)剛才的局面建鞅，顯然鞅之和是鞅，考慮前后期望一樣即可。

當(dāng)然也可以用勢(shì)能函數(shù)做