HDU 4652.Dice

229


题目



点击显/隐题目

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.



The first line contains a number T.(1≤T≤100) The next T line each line contains a query as we mentioned above. (1≤m,n≤106) For second kind query, we guarantee n≤m. And in order to avoid potential precision issue, we guarantee the result for our query will not exceeding 109 in this problem.


For each query, output the corresponding result. The answer will be considered correct if the absolute or relative error doesn't exceed 10-6.


6
0 6 1
0 6 3
0 6 5
1 6 2
1 6 4
1 6 6
10
1 4534 25
1 1232 24
1 3213 15
1 4343 24
1 4343 9
1 65467 123
1 43434 100
1 34344 9
1 10001 15
1 1000000 2000


1.000000000
43.000000000
1555.000000000
2.200000000
7.600000000
83.200000000
25.586315824
26.015990037
15.176341160
24.541045769
9.027721917
127.908330426
103.975455253
9.003495515
15.056204472
4731.706620396




题解


求m面骰子投出连续n次相同/不相同的数学期望


根据正向推概率,逆向推期望的原则来看,我们应该采取从后往前推得形式来计算这道题

首先先来分析dp的意义
对于第一种情况而言,需要求连续n次相同的期望
如果用dp[i]表示i个相同的期望
对于任意一种情况,都有对于i1/m的概率和前一数字相同,也有(m-1)/m的概率和前一数字不同
也即: dp[i]可以转移至dp[1]dp[i+1]
该函数无后效性,并且我们只能得到 dp[i+1]=(1/m)*dp[i]dp[1] += ((m-1)/m)*dp[i] 两个式子
因此,应该换一种含义,使dp可以逆向推出答案

dp[i]表示已经有i个连续,到n个连续的期望
那么很显然 dp[n] = 0
并且dp[0] = dp[1] + 1 (对于0个相同,显然随便投一个数字都可以满足要求)
而且根据含义,有 $dp[i] = 1 + frac{1}{m} times dp[i+1] + frac{m-1}{m} times dp[1]$

剩下就是数学化简过程了
\begin{align*} dp[i] &= 1 + \frac{1}{m} \times dp[i+1] + \frac{m-1}{m} \times dp[1] \\ dp[i] - dp[1] &= 1 + \frac{1}{m} \times (dp[i+1] - dp[1]) \\ dp[i] - dp[1] &= m \times (dp[i-1] - dp[1] - 1) \\ 令 a_i &= dp[i]-dp[1] \\ a_i &= m \times a_{i-1} - m \\ a_i &= m^2 \times a_{i-2} - m^2 - m \\ &…… \\ a_i &= m^{i-1} \times a_1 - \frac{m^i-m}{1-m} \\ dp[i] - dp[1] &= - \frac{m-m^i}{1-m} \\ dp[i] &= dp[1] + \frac{m^i-m}{1-m} \\ \\ dp[1] &= dp[n] - \frac{m^n-m}{1-m} \\ dp[0] &= dp[n] - \frac{m^n-m}{1-m} + 1 \\ dp[0] &s= \frac{m^n-m}{m-1} + 1 \end{align*} ${% endraw %} 也即,对于第一种情况,答案就是 $\frac{m^n-m}{m-1} + 1$ 第二种情况同理 按照相同的概念可以推出 {% raw %}$ \begin{align*} dp[0] &= 1 + dp[1] \\ dp[i] &= \frac {\sum_{k=1}^{i}dp[k]}{m} + \frac{m-i}{m}\times dp[i+1] \\ dp[i-1] &= \frac {\sum_{k=1}^{i-1}dp[k]}{m} + \frac{m-i+1}{m} \times dp[i] \\ 则 dp[i] - dp[i-1] &= \frac{1}{m} \times dp[i] + \frac{m-i}{m}\times dp[i+1] - \frac{m-i+1}{m} \times dp[i]) \\ dp[i] - dp[i-1] &= \frac{m-i}{m}\times (dp[i+1] - dp[i]) \\ dp[i] - dp[i-1] &= \frac{m}{m-i+1} \times (dp[i-1]-dp[i-2]) \\ dp[i-1] - dp[i] &= \frac{m}{m-i+1} \times (dp[i-2]-dp[i-1]) \\ \\ dp[0] - dp[1] &= 1 \\ dp[1] - dp[2] &= \frac{m}{m-1} \times 1 \\ dp[2] - dp[3] &= \frac{m}{m-2} \times \frac{m}{m-1} \times 1 \\ &……\\ dp[n-1] - dp[n] &= \prod_{j=0}^{n-1} \frac{m}{m-j} \\ \therefore dp[0] - dp[n] &= \sum_{i=0}^{n-1} \prod_{j=0}^{i} \frac{m}{m-j} \\ dp[0] &= \sum_{i=0}^{n-1} \prod_{j=0}^{i} \frac{m}{m-j} \end{align*} ${% endraw %} 最后要计算的就是 {% raw %}$\sum_{i=0}^{n-1} \prod_{j=0}^{i} \frac{m}{m-j}${% endraw %} `O(n)`的时间可以得到答案 # 代码 {% fold 点击显/隐代码 %}```cpp Dice https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份 #include double pow(double a, int n) { if (n == 0) return 1.0; double ans = pow(a, n >> 1); return ans * ans * (n & 1 ? a : 1); } double calc1(int n, int m) { return (pow(m, n) - m) / (m - 1) + 1; } double calc2(int n, int m) { double sum = 0.0; double p = 1.0; for (int i = 0; i < n; ++i) { p *= (double)m / (m - i); sum += p; } return sum; } int main() { int T; int c, n, m; while (scanf("%d", &T) != EOF) { while (T--) { scanf("%d%d%d", &c, &m, &n); double (*calc)(int, int) = (!c ? &calc1 : &calc2); printf("%.16f\n", calc(n, m)); } } return 0; } ```
发布评论
  • 点击查看/关闭被识别为广告的评论