盒子
盒子
文章目录
  1. 题目
  2. 题意
  3. 思路
  4. 代码

HDU 4987 Little Pony and Dice(概率dp)

题目

源地址:http://acm.hdu.edu.cn/showproblem.php?pid=4987

题意

有一个 m 面的均匀骰子([1, m]),然后从 0 出发,根据扔的数字,决定向前走的步数,走到 ≥n 时就停止。
求刚好在 n 停止的概率。要求误差 10−5 以内。(1≤m,n≤1e9)

思路

  1. 当 m 很大时,概率会接近 0,由于误差 10−5,当 m≥600000 时,直接返回 0

  2. 当n<=m时,到n的概率为 ((1+(1/m))^(n-1))/m
    计算过程如下:
    C(n-1,0)/m + C(n-1,1)/m^2 + …. + C(n-1,n-1)/m^n 即一步走到,两步走到,n步走到
    提出一个1/m, C(n-1,0)+C(n-1,1)/m+…+C(n-1,n-1)/m^(n-1) = (1+1/m)^(n-1)

  3. 当n>m,且m比较小
    设dp[i]为走到i的概率,s[i]为前i个概率和
    if (i <= m) dp[i] = s[i - 1] / m; //i之前的走一步到达i
    else dp[i] = (s[i - 1] - s[i - 1 - m]) / m; //前m个走一步到达i
    多测试几个数字,会发现当n比较大的时候,答案会收敛于 2/(m+1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#define pb push_back
#define debug puts("=====================");
using namespace std;
typedef long long ll;
int m, n;
const int N = 1000000;
double dp[N + 100], s[N + 100];
int main () {
while(~scanf("%d%d", &m, &n)) {
if (m >= 600000) puts("0.00000");
else {
if (n <= m) printf("%.5lf\n", pow(1 + 1.0 / m, n - 1) / m);
else {
dp[0] = 1, s[0] = 1;
for (int i = 1; i <= n; i++) {
if (i <= m) dp[i] = s[i - 1] / m;
else dp[i] = (s[i - 1] - s[i - 1 - m]) / m;
s[i] = s[i - 1] + dp[i];
if (i >= m && abs(dp[i] - 2. / (m + 1)) <= 1e-9) {
n = i;
break;
}
}
printf("%.5lf\n", dp[n]);
}
}
}
return 0;
}