只講用法。
一般的情況是構造勢能函數，使得操作一次的勢能期望減少 \(1\)，那么期望操作次數就是初始勢能減終止時的勢能。
當然這顯然是很淺薄的理解。

CF1025G Company Acquisitions *3200

定義時刻\(i\)的局面為\(A_i\)，\(f(x)\)為具有\(x\)個未選中點的勢能函數。
定義\(\varphi(A_i)\)為局面\(A_i\)所有點的勢能函數之和。
令\(X_i=\varphi(A_i)+i\)
使得\(E(X_{n+1}-X_n|X_n,....X_0)=0\)，即\(E(\varphi(A_{n+1})-\varphi(A_n)|X_n,....X_0)=-1\)
令一次操作隨機選擇的點為\(u,v\)，具有的未選中點個數分別為\(x,y\)。
顯然\(\frac{f(x+1)+yf(0)+f(y+1)+xf(0)}{2}=f(x)+f(y)-1\)
如果對于任意\(u,v\)，等式成立，則令\(f(0)=0,2f(x)-1=f(x+1)\)
則\(f(x)=1-2^{x}\)
那么答案即為\(E(t)=E(\varphi(A_0))-\varphi(A_t)\)
\(=\varphi(A_0)-(1-2^{n-1})\)

CF1479E School Clubs *3500

定義與上題類似
容易列出等式\(\large E(\varphi(A_{p+1})-\varphi(A_p))=\large\frac{1}{n}\sum_{i=1}^{m}\frac{a_i}{2}[f(a_i-1)+f(1)-f(a_i)+\frac{1}{n}\sum_{j\neq i}a_j(f(a_j+1)+f(a_i-1)-f(a_j)-f(a_i))]=-1\)
化簡即得\(\large f(1)+\frac{1}{n}\sum_{i=1}^{m}a_i[(2n-a_i)[f(a_i-1)-f(a_i)]+\frac{1}{n}\sum_{j\neq i}a_j(f(a_j+1)-f(a_j))]=-2\)
\(\large f(1)+\frac{1}{n}\sum_{i=1}^{m}a_i[(2n-a_i)[f(a_i-1)-f(a_i)]+(n-a_i)(f(a_i+1)-f(a_i))]=-2\)
令\(\large f(0)=0,f(1)=-2\)，則
\(\large \sum_{i=1}^{m}a_i[(2n-a_i)f(a_i-1)-(3n-2a_i)f(a_i)+(n-a_i)f(a_i+1)]=0\)
令\(\large (2n-s)f(s-1)-(3n-2s)f(s)+(n-s)f(s+1)=0\)，等式恒成立。
可以得到\(\large f(s+1)=\frac{(3n-2s)f(s)-(2n-s)f(s-1)}{n-s}\)
將\(\large f(s)\)表示為\(\large \frac{p}{q}\)的形式后，就可以實現\(\large O(m\log(mod)+n)\)的遞推了。

CF1575F Finding Expected Value *2900

推式子是簡單的，這里就不提了。
跟之前有不同的是這次的\(E(\varphi(A_0))\neq \varphi(A_0)\)，需要求一下初始局面的期望勢能。
根據期望的線性性，得\(E(\sum_{i=0}^{k-1}f(a_i))=\sum_{i=0}^{k-1}E(f(a_i))\)
令\(p_i\)為序列中新增\(i\)個與給定值\(x\)相同的數的概率，\(c\)為序列中\(-1\)的個數。
顯然\(\large p_i=\frac{\binom{c}{i}(k-1)^{c-i}}{k^c}\)
所以\(E(f(a_i))=\sum_{j=0}^{c}p_jf_{a_i+j}\)，可以任意模數NTT卷積。
但這是不必要的，因為本質不同的\(a_i\)只有\(O(\sqrt{n})\)個，所以有了可接受的復雜度\(O(n\sqrt{n})\)

ABC249Ex Dye Color *3487

難度基本全在這個定理上。
照例，我們列出等式，令\(p=a_s\)，則\(\sum_{s=1}^{n}\frac{1}{2^n}\sum_{i=0}^{n}\frac{1}{\binom{n}{i}}\sum_{j=0}^{p}\binom{p}{j}\binom{n-p}{i-j}(\binom{n-1}{i-1}f(p-j+1)+\binom{n-1}{i}f(p-j)))\)
\(=-1+\sum_{s=1}^{n}f(p)\)
那么只要使得\(f(x)-\sum_{i=0}^{n}\frac{1}{2^n}\frac{1}{\binom{n}{i}}\sum_{j=0}^{x}\binom{x}{j}\binom{n-x}{i-j}(\binom{n-1}{i-1}f(x-j+1)+\binom{n-1}{i}f(x-j)))=\frac{x}{n}\)就行了。容易從\(O(n^3)\)優化到\(O(n^2)\)

yuki1784 Not a star yet...

好久沒有更新了。。。
實際上我不講鞅相關理論的原因在于我根本沒有深刻理解。。。
你看，這道題就是這樣。
令 \(1\) 邊個數為 \(X\)，\(2\) 邊個數為 \(Y\)。
對一個圖 \(G\) 定義 \(\varphi(G)\) 為其的勢能，對每個點定義勢能為 \(f_{i,j}\) 代表其連了 \(i\) 個 \(1\) 邊，\(j\) 個 \(2\) 邊。
對于一個點的勢能，我們期望其在一次操作后減少 \(\frac{1}{n}\)。
終止條件是星形圖 \(\varphi(G_T)=0\)，答案為初始圖的勢能 \(\varphi(G_0)\)。
令 \(P=\frac{n(n-1)}{2}-(n-2)\)，\(Q=n-i-j\)，
不難得到轉移
\(P(X+2Y)f(i,j) = (Q(i+2j)+(P-Q+1)((X-i)+2(Y-j))) f(i,j) + (P-Q)if(i-1,j) + (P-Q)j f(i,j-1) + (Q-1)(X-i)f(i+1,j) + (Q-1) 2(Y-j) f(i,j+1) + \frac{(X+2Y)P}{N}\)
（聯考搬題人復制題解改都不帶改是吧，連錯誤都一模一樣，我懷疑你真的過了嗎）
可以發現 \(f_{i,j}\) 可以被 \(f_{0,*}\) 線性組合，所以只用做一個 \(O(Y)\) 個變量的高斯消元，復雜度 \(O(n^3)\)。
行列式為 \(0\) 怎么辦？官解有存在性證明，見 editorial。