1. 题目描述
对于m面的骰子。有两种查询，查询0表示求最后n次摇骰子点数相同的期望；查询1表示最后n次摇骰子点数均不相同的期望。2. 基本思路由期望DP推导，求得最终表达式。(1) 查询0 不妨设$dp[k]$表示当前已经有k次相同而最终实现n次相同的期望。 \begin{align} dp[0] &= 1 + dp[1] \notag \\ dp[1] &= 1 + \frac{1}{m}dp[2] + \frac{m-1}{m}dp[1] \notag \\ dp[2] &= 1 + \frac{1}{m}dp[3] + \frac{m-1}{m}dp[1] \notag \\ &\cdots \notag \\ dp[n-1] &= 1 + \frac{1}{m}dp[n] + \frac{m-1}{m}dp[1] \notag \\ dp[n] &= 0 \end{align} 两两相减可得。 \begin{align} dp[0]-dp[1] &= \frac{1}{m}(dp[1]-dp[2]) \notag \\ dp[1]-dp[2] &= \frac{1}{m}(dp[2]-dp[3]) \notag \\ dp[2]-dp[3] &= \frac{1}{m}(dp[3]-dp[4]) \notag \\ &\cdots \notag \\ dp[n-2]-dp[n-1] &= \frac{1}{m}(dp[n-1]-dp[n]) \end{align} 由$dp[0]=1+dp[1], dp[0]-dp[1]=1$代入可得。 \begin{align} dp[0]-dp[1] &= 1 \notag \\ dp[1]-dp[2] &= m \notag \\ dp[2]-dp[3] &= m^2 \notag \\ &\cdots \notag \\ dp[n-1]-dp[n] &= m^{n-1} \end{align} 显然是一个等比数列，累加后可得$dp[0]-dp[n]=dp[0]$. \begin{align} dp[0] = \frac{m^n-1}{m-1} \end{align}（2）查询1
不妨设$dp[k]$表示当前已经有k个不同而最终实现n个不同的期望。 \begin{align} dp[0] &= 1 + dp[1] \notag \\ dp[1] &= 1 + \frac{1}{m}dp[1] + \frac{m-1}{m}dp[2] \notag \\ dp[2] &= 1 + \frac{1}{m}dp[1] + \frac{1}{m}dp[2] + \frac{m-2}{m}dp[3] \notag \\ &\cdots \notag \\ dp[n-1] &= 1 + \Sigma_{i=1}^{n-1}{\frac{1}{m}dp[i]} + \frac{m-(n-1)}{m}dp[n] \notag \\ dp[n] &= 0 \end{align} 两两相减可得。 \begin{align} dp[0]-dp[1] &= \frac{m-1}{m}(dp[1]-dp[2]) \notag \\ dp[1]-dp[2] &= \frac{m-2}{m}(dp[2]-dp[3]) \notag \\ &\cdots \notag \\ dp[n-2]-dp[n-1] &= \frac{m-(n-1)}{m}(dp[n-1]-dp[n]) \end{align} 由$dp[0]=1+dp[1], dp[0]-dp[1]=1$代入累加后可得。 \begin{align} dp[0] = \Sigma_{i=1}^{n} \frac{m^i}{\prod_{j=0}^{i-1}(m-j)} \end{align}3. 代码1 /* 4652 */ 2 #include3 #include 4 #include 5 #include