SGU495 Kids and Prices[期望DP]

也许更好的阅读体验
$Description$Description
有 $n$n个格子，每次等概率随机给一个格子染色，问涂 $m$m次后期望有多少格子被染色了

$Solution$Solution
设 $f\left[i\right]$f[i]表示涂 $i$i次后期望有多少格子被染色了
现在进行第 $i$i次染色，有两种情况

1. 有 $\frac{f[i-1]}{n}$nf[i−1]​的概率涂到已经涂过的格子
2. 有 $\frac{n-f[i-1]}{n}$nn−f[i−1]​的概率涂到没涂过的格子

需要注意的是，无论是以上哪种，都已经有 $f[i-1]$f[i−1]个格子被染色了
所以有
$f\left[i\right]=\frac{f[i-1]}{n}\cdot 0+\frac{n-f[i-1]}{n}\cdot 1+f[i-1]$f[i]=nf[i−1]​⋅0+nn−f[i−1]​⋅1+f[i−1]
将其化简
$f\left[i\right]=\frac{n-f[i-1]}{n}+f[i-1]=\frac{n-1}{n}f[i-1]+1$f[i]=nn−f[i−1]​+f[i−1]=nn−1​f[i−1]+1
此时该式就是一个等差数列套等比数列
于是我们可以求其通项公式，博主懒得求了写下大致过程

令 $k=\frac{n-1}{n}$k=nn−1​
$f_n=k{f}_{n-1}+1$fn​=kfn−1​+1
$f_n+\frac{1}{k-1}=k{f}_{n-1}+\frac{k}{k-1}$fn​+k−11​=kfn−1​+k−1k​
$f_n+\frac{1}{k-1}=k(f_{n-1}+\frac{1}{k-1})$fn​+k−11​=k(fn−1​+k−11​)
令 $g_n=f_n+\frac{1}{k-1}$gn​=fn​+k−11​
则 $g_n=k{g}_{n-1}$gn​=kgn−1​
怎么求 $g_n$gn​就不用说了吧
$f_n=g_n-\frac{1}{k-1}$fn​=gn​−k−11​
$f_n$fn​也能求出来了

初值 $f\left[0\right]=0$f[0]=0答案为 $f\left[m\right]$f[m]
应正向循环

本篇博客亦被收进期望总结

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧