期望

\(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}{d}\) 的機率随機選擇一條邊走過去。

求 \(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\) 點不動。

\(n \le 100000\) ，\(m \le 200000\)

\[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)\) 。

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\) 号點。

\[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]}{(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}

帶入求值即可。

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][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]]
);
           

• 轉移 \(dp[i][j][1]\) ：

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]]
);
           

難點：因為在上一次換教室時是 機率 交換，是以不一定會換，是以要把兩種情況的都加上（上面寫了）。

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=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);