有一个mm面的骰子,不停地掷骰子,求以下两种情况的期望步数:

  1. 连续出现nn个相同的时候停止
  2. 连续出现nn个不同的时候停止

n,m106n,m\le 10^6

HDU4652

Solution

首先很容易设出一个dp:f[i]f[i]表示连续出现ii个相同时的期望步数,g[i]g[i]表示连续出现ii个不同时的期望步数

有两种比较套路的处理方法(其实也很容易想到,这里只详细说明ff的求法,gg类似):

  • 差分:

    f[i+1]f[i+2]=m(f[i]f[i+1]) f[i + 1] - f[i + 2] = m(f[i] - f[i + 1])

    特别地,

    f[0]=1mf[1]+m1mf[1]+1f[0]f[1]=1 \begin{aligned} &f[0] = \frac{1}{m}f[1] + \frac{m-1}{m}f[1] + 1\\ \Rightarrow &f[0] - f[1] = 1 \end{aligned}

    所以我们有:

    f[0]f[1]=1f[1]f[2]=mf[2]f[3]=m2...f[n1]f[n]=mn1 \begin{aligned} f[0] -& f[1] = 1\\ \\ f[1] -& f[2] = m\\ \\ f[2] -& f[3] = m^2\\\\ &...\\\\ f[n - 1] - &f[n] = m^{n-1} \end{aligned}

    对上述式子求和可以得到:

    f[0]f[n]=i=0n1mi f[0] - f[n] = \sum_{i=0}^{n-1}m^i

    因为f[n]=0f[n] = 0,所以直接得到 ,这个也可以用等比数列求和随便化一下,不过gg的式子化不了

  • 把所有状态都用f[0]f[0]表示

    其实这个做法和差分本质是一样的,直接代入即可,这里就不赘述了

Summary

当dp方程中出现一些比较难处理的,与ii无关的项的时候可以考虑差分将其抵消,推导出差分的关系,再通过求和计算

Code

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

int N, M, op;

inline void Solve ()
{
if (!op)
{
LL ans = 0;
for (int i = 0; i <= N - 1; ++i) ans += pow(M, i);
printf("%lld\n", ans);
}
else
{
double ans = 0, sum = 1;
for (int i = 0; i <= N - 1; ++i)
{
sum = sum * M / (M - i);
ans += sum;
}
printf("%.7lf\n", ans);
}
}

inline void Input ()
{
scanf("%d%d%d", &op, &M, &N);
}

int main()
{
#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif
int Testcase;
while (scanf("%d", &Testcase) != EOF)
{
while (Testcase--)
{
Input();
Solve();
}
}
return 0;
}

P.S.P.S.这道题不知道为什么用read <int>()就会T,改成scanf就A了...