题面
Vjudge
有一个
m
面骰子
询问，连续出现
n
个相同的时候停止的期望
连续出现
n
个不同的时候停止的期望
题解
考虑两种分开询问来算。
第一种：
设
f
[
i
]
表示已经有连续的
i
个相同时，到达目标状态的期望。
f
[
i
]
=
1
m
f
[
i
+
1
]
+
m
−
1
m
f
[
1
]
+
1
相邻两项作差，得到
m
(
f
[
i
+
1
]
−
f
[
i
]
)
=
f
[
i
+
2
]
−
f
[
i
+
1
]
按照顺序列出来
f
[
0
]
−
f
[
1
]
=
1
f
[
1
]
−
f
[
2
]
=
m
f
[
2
]
−
f
[
3
]
=
m
2
…
f
[
n
−
1
]
−
f
[
n
]
=
m
n
−
1
将所有式子相加起来
f
[
0
]
−
f
[
n
]
=
m
n
−
1
1
−
m
f
[
n
]
=
0
，这样就知道了
f
[
0
]
所以
A
n
s
=
f
[
0
]
=
m
n
−
1
1
−
m
考虑第二种询问
设
f
[
i
]
表示连续
i
个不同的数字，到达目标状态的期望
f
[
i
]
=
m
−
i
m
f
[
i
+
1
]
+
f
[
1
]
+
f
[
2
]
+
f
[
3
]
+
.
.
.
f
[
i
−
1
]
+
f
[
i
]
m
还是相邻两项作差让后相加，算出答案
A
n
s
=
∑
i
=
0
n
−
1
∏
j
=
0
i
m
m
−
j
#include<cstdio>
#include<cmath>
using namespace std;
double Solve1(int m,int n){return (pow(m,n)-1.0)/(m-1.0);}
double Solve2(int m,int n)
{
double ret=1,d=1;
for(register int j=1;j<n;++j)d=1.0*m/(m-j)*d,ret+=d;
return ret;
}
int main()
{
register int T,opt,n,m;
while(scanf("%d",&T)!=EOF)while(T--)
{
scanf("%d%d%d",&opt,&m,&n);
printf("%.9lf\n",!opt?Solve1(m,n):Solve2(m,n));
}
}