期望 概率DP
期望
\(x\) 的期望 \(E(x)\) 表示平均情況下 \(x\) 的值。
令 \(C\) 表示常數， \(X\) 和 \(Y\) 表示兩個隨機變量。
-
\(E(C)=C\)
-
\(E(C \times X)=C \times E(X)\)
-
\(E(X+Y)=E(X)+E(Y)\) 期望的線性性
-
\(E(XY)\) 不一定等于 \(E(X) \times E(Y)\)
期望練習：
題意：
\(n\) 個格子從左往右排成一排，\(m\) 次操作。
每次操作隨機選擇一個區間 \([l,r]\) ，將里面所有格子涂黑。
求 \(m\) 次操作完畢后，被涂黑的格子數量的期望。
\(solution\)：
期望的線性性，答案等于每個格子被涂黑的概率之和。
對于某個格子，假設一次操作涂黑它的概率為 \(p\) ，則 \(m\) 次操作涂黑它的概率為 \(1-(1-p)^m\)。
期望(概率)DP
- 游走I
題意：
\(n\) 個點 \(m\) 條邊的有向無環圖，保證 \(1\) 可以到達每個點，且每個點可以到達 \(n\) 號點。如果現在在 \(x\) ，\(x\) 連了 \(d\) 條邊出去，那么會以 \(\dfrac{1}ze8trgl8bvbq\) 的概率隨機選擇一條邊走過去。
求 \(1\) 游走到 \(n\) 的期望步數。
$n \le 100000 $ ，\(m \le 200000\)
\(solution\) ：
記憶化搜索。
設 \(e[x]\) 表示 \(x\) 走到 \(n\) 的期望步數。
\[e[n]=0 \]\[e[x]= 1 + \dfrac{\sum_{y}^{y \in son[x]}e[y]}{d[x]} \]復雜度：\(O(n + m)\) 。
$\texttt{code}$ void dfs(ll x) {if(dp[x]!=-1) return;ll cnt=0;for(ll i=hea[x];i;i=nex[i]){dfs(ver[i]);cnt+=dp[ver[i]];}dp[x]=(cnt*inv[x]+1)%mod; }for(ll i=1;i<=m;i++) {u=rd(),v=rd();add(u,v),outd[u]+=1; } for(ll i=1;i<=n;i++) inv[i]=Pow(outd[i],mod-2); dfs(1); printf("%lld\n",dp[1]);- 游走II
題意：
\(n\) 個點 \(m\) 條邊的有向無環圖，保證 \(1\) 可以到達每個點，且每個點可以到達 \(n\) 號點。如果現在在 \(x\) ，\(x\) 連了 \(d\) 條邊出去，那么會以 \(\dfrac{1}{d+1}\) 的概率隨機選擇一條邊走過去，或者以 \(\dfrac{1}{d+1}\) 的概率待在 \(x\) 點不動。
求 \(1\) 游走到 \(n\) 的期望步數。
\(n \le 100000\) ，\(m \le 200000\)
\(solution\) ：
\[e[x]=\dfrac{e[x]+\sum_{y}^{y \in son[x]}{e[y]}}{d[x]+1}+1 \]有 \(e[x]\) 怎么辦？化簡！
\[e[x] \times (d[x]+1)=e[x]+d[x]+1+\sum_{y}^{y \in son[x]}{e[y]} \]\[e[x] \times d[x]=d[x]+1+\sum_{y}^{y \in son[x]}{e[y]} \]結論：
\[e[x]=\dfrac{d[x]+1+\sum_{y}^{y \in son[x]}{e[y]}}{d[x]} \]復雜度：\(O(n+m)\) 。
$\texttt{code}$ void dfs(ll x) {if(dp[x]!=-1) return;ll cnt=0;for(ll i=hea[x];i;i=nex[i]){dfs(ver[i]);cnt+=dp[ver[i]];}dp[x]=(cnt+outd[x]+1)*inv[x]%mod; }for(ll i=1;i<=m;i++) {u=rd(),v=rd();add(u,v),outd[u]+=1; } for(ll i=1;i<=n;i++) inv[i]=Pow(outd[i],mod-2); dfs(1); printf("%lld\n",dp[1]);- 游走III
題意：
\(n\) 個點 \(m\) 條邊的有向無環圖，保證 \(1\) 可以到達每個點，且每個點可以到達 \(n\) 號點。如果現在在 \(x\) ，\(x\) 連了 \(d\) 條邊出去，那么會以 \(\dfrac{1}{d+1}\) 的概率隨機選擇一條邊走過去，或者以 \(\dfrac{1}{d+1}\) 的概率回到 \(1\) 號點。
求 \(1\) 游走到 \(n\) 的期望步數。
\(n \le 100000\) ，\(m \le 200000\)
\(solution\) ：
\[e[x]=\dfrac{e[1]+\sum_{y}^{y \in son[x]}{e[y]}}{d[x]+1}+1 \]有 \(e[1]\) 怎么辦？另外定義轉移方程！
設：
\[e[x]=f[x] * e[1]+g[x] \]則有：
\[e[1]=\dfrac{g[x]}{1-f[x]} \]帶入轉移方程式：
\[e[x]=\dfrac{e[1]+\sum_{y}^{y \in son[x]}{e[y]}}{d[x]+1}+1 \]\[e[x] = \dfrac{e[1]+\sum_{y}^{y \in son[x]}{(f[y] \times e[1] + g[y])}}{d[x]+1}+1 \]\[e[x] = \begin{pmatrix}\dfrac{e[1]+\sum_{y}^{y \in son[x]}{f[y] \times e[1]}}{d[x]+1}\end{pmatrix} + \begin{pmatrix}1+\dfrac{\sum_{y}^{y \in son[x]}{g[y]}}{d[x]+1}\end{pmatrix} \]\[e[x] = \begin{pmatrix}\dfrac{1+\sum_{y}^{y \in son[x]}{f[y]}}{d[x]+1}\end{pmatrix} \times e[1] + \begin{pmatrix}1 + \dfrac{\sum_{y}^{y \in son[x]}{g[y]}}{d[x]+1} \end{pmatrix} \]因為 \(e[x]=f[x] * e[1]+g[x]\) ，所以最終可以得出結論：
\[f[x] = \dfrac{1+\sum_{y}^{y \in son[x]}{f[y]}}{d[x]+1} \]\[g[x] = 1 + \dfrac{\sum_{y}^{y \in son[x]}{g[y]}}{d[x]+1} \]\[e[1]=\dfrac{g[x]}{1-f[x]} \]帶入求值即可。
$\texttt{code}$ void dfs(ll x) {if(f[x]!=-1) return;ll cntf=0,cntg=0;for(ll i=hea[x];i;i=nex[i]){dfs(ver[i]);cntf+=f[ver[i]];cntg+=g[ver[i]];}f[x]=(cntf+1)*inv[x]%mod;g[x]=(cntg*inv[x]%mod+1ll)%mod; }for(ll i=1;i<=m;i++) {u=rd(),v=rd();add(u,v),outd[u]+=1; } for(ll i=1;i<=n;i++) inv[i]=Pow(outd[i]+1,mod-2); dfs(1); printf("%lld\n",g[1]*Pow(((1-f[1]+mod)%mod+mod)%mod,mod-2)%mod);其他習題
P1850 換教室
狀態：設 \(dp[i][j][0/1]\) 來表示當前為第 \(i\) 個階段，連同這一次已經用了 \(j\) 次換教室的機會，當前這次換 \((1)\) 不換 \((0)\) 的最小期望路程總和。
轉移：
- 轉移 \(dp[i][j][0]\) ：
- 轉移 \(dp[i][j][1]\) ：
難點：因為在上一次換教室時是 概率 交換，所以不一定會換，所以要把兩種情況的都加上(上面寫了)。
$\texttt{code}$ memset(dis,inf,sizeof(dis)); for(int i=1;i<=v;i++) dis[i][i]=0; int x,y,eg; for(int i=1;i<=e;i++) x=rd(),y=rd(),eg=rd(),dis[x][y]=dis[y][x]=min(dis[x][y],eg); for(int k=1;k<=v;k++) for(int i=1;i<=v;i++) for(int j=1;j<=v;j++)dis[i][j]=dis[j][i]=min(dis[i][j],dis[i][k]+dis[k][j]); for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=1;k++) dp[i][j][k]=1.0*inf; dp[1][0][0]=dp[1][1][1]=0; for(int i=2;i<=n;i++) {for(int j=0;j<=min(i,m);j++){dp[i][j][0]=fmin(dp[i-1][j][0] + dis[c[i-1]][c[i]],dp[i-1][j][1] + p[i-1]*dis[d[i-1]][c[i]] + (1.0-p[i-1])*dis[c[i-1]][c[i]]);if(j!=0) dp[i][j][1]=fmin(dp[i-1][j-1][0] + p[i]*dis[c[i-1]][d[i]] + (1-p[i])*dis[c[i-1]][c[i]],dp[i-1][j-1][1] + p[i-1]*p[i]*dis[d[i-1]][d[i]] + p[i-1]*(1-p[i])*dis[d[i-1]][c[i]] + (1-p[i-1])*p[i]*dis[c[i-1]][d[i]] + (1-p[i-1])*(1-p[i])*dis[c[i-1]][c[i]]);} } ans=1.0*inf; for(int j=0;j<=m;j++) for(int k=0;k<=1;k++) ans=fmin(ans,dp[n][j][k]); printf("%.2lf\n",ans);P3750 [六省聯考2017]分手是祝愿
先考慮求出最小操作次數 \(c\) 。
考慮從大到小枚舉 \(n\) 盞燈，若當前這盞燈是亮的，那么求將這盞燈熄滅，并更新左右它的約數。
若初始局面需要的最小操作次數小于等于 \(k\) ，顯然操作次數為最小操作次數。
我們可以預處理出 \(dp(i)\) 表示有 \(i\) 個選擇變為 \(i-1\) 個選擇的最小操作次數。
則轉移為：
\[dp(i)=\dfrac{i}{n}+\left(1-\dfrac{i}{n}\right)\times(1+dp(i)+dp(i+1)) \]化簡得：
\[dp(i)=1+\dfrac{(n-i)\times(dp(i+1)+1)}{i} \]則最終答案期望為：
\[k+\sum_{i=k+1}^{c}dp(i) \]別忘了最終答案乘上 \(n!\) 。
$\texttt{code}$ n=rd(),k=rd(); for(int i=1;i<=n;i++) if(rd()) b[i]=true; for(ll i=1;i<=n;i++) for(ll j=i;j<=n;j+=i) yue[j].pb(i); for(int i=n;i>=1;i--) if(b[i]) {for(int j:yue[i]) b[j]^=1;cnt++; } if(cnt<=k) ans=cnt; else {dp[n]=1;for(ll i=n-1;i>=1;i--)dp[i]=(1ll+(1ll*n-i)*(dp[i+1]+1ll)%mod*ksm(i,mod-2)%mod)%mod;for(int i=k+1;i<=cnt;i++) ans=(ans+dp[i])%mod;ans=(ans+k)%mod; } for(ll i=1;i<=n;i++) ans=ans*i%mod; printf("%lld\n",ans); 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎總結
