# [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.

## 题目大意

2.当生成的最后n种字符都互不相同时停止，求期望长度

## 解决思路

$F[i]=\frac{1}{m}F[i+1]+\frac{m-1}{m}f[1]+1$

$G[i]=m^i$

$F[1]=m+m^2+m^3+m^4+……+m^{n-1}$

$F[0]=1+m+m^2+m^3+……+m^{n-1}$

$F[0]=\frac{m^{n+1}-m}{m-1}$

$F[i]=\frac{m-i}{m}F[i+1]+\sum_{k=1}^{i}\frac{1}{m}F[k]$

$G[i]=\frac{m}{m-i-1}G[i+1]$

$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})$

HNCJ OIer