Probabilistic DP problemset#1
冷靜好好想，好好推。
用狀態 $f[i][j][0/1]$ 表示當前剩有 $i$ 隻白鼠，$j$ 隻黑鼠時，princess 贏的概率（$0$ 表示當前為 princess’ s turn，$1$ 表示 dragon’s turn）。則有轉移：
\[f[i][j][0]=\frac{i}{i+j}+\frac{j}{i+j}\times f[i][j-1][1]\] \[f[i][j][1]=\frac{j}{i+j}\times(\frac{i}{i+j-1}f[i-1][j-1][0]+\frac{j-1}{i+j-1}f[i][j-2][0])\]複雜度：$O(WB)$。
對於當前某個狀態的期望 $f$，以及它能以概率 $p$ 轉移到另一狀態之期望 $g$，則有：
\[\begin{align*} &f=1+pg+(1-p)f\\ \Rightarrow &f=g+\frac{1}{p} \end{align*}\]注意到最後合法的狀態是若干個環以及長度為 $1$ 與孤立點至多一個，於是可用狀態 $f[i][j][k]$ 表示當前尚有 $i$ 個孤立點，$j$ 個長度為 $1$ 的鏈和 $k$ 個長度大於 $1$ 的長鏈。則有：
\[\begin{align*} f[i][j][k]&=\frac{1}{p}+\sum_{i',j',k'}p_{i'j'k'}f[i'][j'][k'] \end{align*}\]$(i’,j’,k’)$ 為可轉移到的狀態。$p$ 為能轉移出去的概率，$p_{i’j’k’}$ 為轉移出去的情況是 $(i’,j’,k’)$ 的概率。
複雜度：$O(n^3)$。
由於期望是最低層產生的貢獻，故祇要考慮下至上的傳染。用 $f[u]$ 表示當前結點 $u$ 由其子樹或外界感染的概率。然後按最小層數考慮統計答案，在第 $d$ 層，產生的貢獻的情況為：上層全不被外界感染且第 $(d-1)$ 層不被 $d$ 層結點感染且 $d$ 層結點至少有一個被感染。
複雜度：$O(n+\max\lbrace q,b\rbrace)$ 或 $O(n\log \max\lbrace q,b\rbrace)$。
用狀態 $f[i][j][k]$ 表示考慮至第 $i$ 張牌，當前選擇了 $j$ 張牌，總和為 $k$ 的概率，則有：
\[f[i][j][k]=f[i-1][j][k]+f[i-1][j-1][k-x[i]]\times\frac{j}{n-j+1}\]但答案並非 $\sum{f[n][j][k],a<k\leq b}$。會有重復，故需枚舉最後取了哪個數，可以將此數除去而後重做 dp，第 $i$ 張牌的貢獻為：
\[\sum f[n-1][j][k]\times\frac{1}{n-j}(k\leq a\wedge a<k+x[i]\leq b)\]但遮樣 $O(n^4)$ 的複雜度難免會獲得 TLE，故考慮從 $f[n][j][k]$ 中直接扣除 $i$ 的影響進行答案的統計。記 $g[i][j][k]$ 為最後選了 $j$ 張牌，和為 $k$ 且不含 $i$ 的概率，則有：
\[g[i][j][k]=f[n][j][k]-g[i][j-1][k-x[i]]\times\frac{j}{n-j+1}\]遮樣最後的複雜度為： $O(n^3)$。
用狀態 $f[i][j]$ 表示過了 $i$ 天，選了 $j$ 個不同的 orbs 的概率，則有：
\[f[i][j]=f[i-1][j]\times\frac{j}{k}+f[i-1][j-1]\times\frac{k-j+1}{k}\]複雜度，還不會證。
若記 $p_{n}$ 為 $f[n][k]$，有：
\[p_{n}=\left((e^{x/k}-1)^{k}\right)^{(n)}\vert_{x=0}\]不會算。
人類智慧。考慮每个結點 $v$ 被選中的次數的期望 $E[X_v]$，答案為其和。對於某個 $v$，若選擇非 $v$ 至 $1$ 路径上的點都對其期望無影響，故可以轉換為鏈的情況進行考慮。接著可以發現 $v$ 前的點即使變為 good 再被選仍與 $E[X_v]$ 無關，祇需求每次可等概率選 $1,\ldots,n$，當 $1,\ldots, n$ 都被選上時，$n$ 被選中的次數的期望。簡單推導可以發現選完的期望為 $n\sum_{i=1}^{n}\frac{1}{i}$，由對稱性知 $E[n]=\sum_{i=1}^{n}\frac{1}{i}$，故預處理 $\frac{1}{i}$ 前綴和，而後 dfs 記录下每个點的深度即可。
複雜度：$O(n\log n)$ 或 $O(n)$。
$k$ 次生成對於 $i$ 事件有 $D(i,k)$，有：
\[\frac{a_i}{b_i}=\sum_{k=1}^{\infty}\frac{D(i,k)}{R^k}(D(i,k)<R)\]將 $\frac{a_i}{b_i}$ 表示成 $R$ 進制的小數，第 $k$ 位即為 $D(i,k)$。$H(i)$ 為 $i$ 次生成未達終結情況的情況數，有：
\[E=\sum_{i=0}^{\infty}\frac{H(i)}{R^i}\]$H(0)=1$，有遞推式：
\[H(i+1)=H(i)R-\sum_{j=1}^{N}D(j,i)\]無窮級數收斂，求個 $50$ 次即可，但要注意精度問題。
複雜度：$O(TNH)$。$H$ 為迭代計算次數。
用 $f[r]$ 表示最後的要放 $k$ 個 $1$ 的位置上 $0$ 的數目時，要使其變為 $0$ 的期望。則有：
\[f[r]=f[r-1]+C_{n}^2\frac{1}{r^2}\]故答案為：$C_{n}^{2}\sum{\frac{1}{r^2}}$。
複雜度：$O(N\log(N))$ 或 $O(N)$。
當 $m\to\infty$ 時，對於第 $i$ 個 bead 之前期望有 $cnt[i]$ 个 bead。那麼答案就是 $\sum_{i} cnt[i]\cdot p[i]$。而對於 $cnt[i]$，就是考慮其它數的貢獻即可。
複雜度： $O(n^2)$。
記 $f_i$ 為在第 $i$ 天的期望，很容易推出：
\[f_i=1+\min\{f_{i+1}, (1-p_i)f_{a_i}\}\]然而，遮樣的遞推依賴前後狀態，無法線性遞推，但是註意到在某一最優決策下，第一次在 $k$ 使用 option 時，跳回之前狀態，仍會按照第一種轉移，故仍會依賴 $f_k$，故可推出：
\[f_k = \frac{1+(1-p_k)(k-a_k)}{p_k}\]所以決策一定是祇到某一步使用 option，其他均由下一個狀態來轉移。
故答案為枚舉使用 option 的位置得到每一种期望的最小值。