[HDU4652]Dice(动态规划,期望概率)

发布于 2018-04-07  131 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU4652]Dice(动态规划,期望概率)

Description

You have a dice with m faces, each face contains a distinct number. We assume when we tossing the dice, each face will occur randomly and uniformly. Now you have T query to answer, each query has one of the following form:
0 m n: ask for the expected number of tosses until the last n times results are all same.
1 m n: ask for the expected number of tosses until the last n consecutive results are pairwise different.

Tag

动态规划,期望概率

题目大意

给出大小为m的字符集,现在等概率地随机生成字符,问:1.当生成的最后n种字符都相同时停止,求期望长度
2.当生成的最后n种字符都互不相同时停止,求期望长度

解决思路

先看第一问,可以想到设F[i]表示当前结尾有i个字符相同时,还要生成的字符的期望长度,则有
\[F[i]=\frac{1}{m}F[i+1]+\frac{m-1}{m}f[1]+1\]
意义就是,有\(\frac{1}{m}\)的概率生成的字符与当前最后一个相同,则由F[i+1]转移过来;否则,重新从f[1]开始。
那么,一种办法就是以F[1]为主元,然后依次用含F[1]的式子表示出F[2],F[3],F[4]……,最后由于我们是知道F[n]=0的,所以可以解出F[1]。
另一种办法就是差分,设G[i]为差分数组,G[i]=F[i]-F[i+1],把F[i]的表达式带入可以得到
\[G[i]=m^i\]
又因为是差分数组,所以F[1]-F[n]=G[n-1]+G[n-2]+G[n-3]+……+G[1],F[n]=0,所以有
\[F[1]=m+m^2+m^3+m^4+……+m^{n-1}\]
又因为F[0]=F[1]+1,所以
\[F[0]=1+m+m^2+m^3+……+m^{n-1}\]
这是一个等比数列,可以得到
\[F[0]=\frac{m^{n+1}-m}{m-1}\]
所以直接快速幂就好。
然后来看第二问
类似地,设F[i]表示当前结尾有i个字符两两不同时,达到终态的期望长度,则有
\[F[i]=\frac{m-i}{m}F[i+1]+\sum_{k=1}^{i}\frac{1}{m}F[k]\]
意义是,若生成的是与前面i个都不一样的,则由F[i+1]转移过来;否则,生成了一个与前面一样的,由前面每一个转移过来。
同样的,这也可以以F[1]为主元进行加减消元,但复杂了许多。考虑差分。
设\(G[i]=F[i]-F[i+1]\),把F[i]的式子带入,可以得到
\[G[i]=\frac{m}{m-i-1}G[i+1]\]
由F[0]-F[n]=F[0]-F[1]+F[1]-F[2]+F[2]-F[3]+……+F[n-1]-F[n]=G[0]+G[1]+G[2]+G[3]+……+G[n-1],有F[n]=0,所以
\[F[0]=G[0]+\frac{m-1}{m}G[0]+\frac{m-1}{m}\frac{m-2}{m}G[0]+…… \\ +\frac{m-1}{m}……\frac{m-(n-1)}{m}G[0]\]
\[F[0]=G[0]*(1+\frac{m-1}{m}+\frac{m-1}{m}*\frac{m-2}{m}+……+\frac{m-1}{m}*\frac{m-2}{m}*……\frac{m-(m-1)}{m})\]
这个可以用一个变量维护\(\frac{m-i}{m}\)的乘积,然后O(n)计算。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU4652]Dice(动态规划,期望概率)


HNCJ OIer