题面：
m 面骰子,求
1. 出现n个连续相同的停止 ;
2. 出现n个连续不同的停止的期望次数。
(n, m ≤ 10^6 )
解析：
当然要先列式子啦。
用f[i]（g[i]）表示出现i个连续相同（不相同）的停止的期望次数。（期望=1/概率）
当然可秒看出f[1]=1,f[n]=0;
但我们不能顺推，因我们不能确定f[0]的值。那就逆推吧。
当前事件期望=1/概率×后继事件a+1/概率×后续事件b+1。（注意1代表当前情况能向所有已知方向拓展，而无障碍）
f[i]=1/m*f[i+1]（加入与前面相同的数）+(m-1)/m*f[1]（加入与前面不同的数）+1
g[i]=(m-i)/m*g[i+1]+1/m*(g[1]+g[2]+...+g[i])+1（注意到加入的数可与前面任一数相同）
然后推等比或等差。
f(x+2)-f(x+1)=m*(f(x+1)-f(x))
g(x+2)-g(x+1)=(m/(m-x-1))*(g(x+1)-g(x)) （ps:别直接乘这玩意儿，不开long double会掉精度）
以此计算即可。
代码
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
int n,m,T,op;
il double calc1(re int m,re int n)
{
double ans=0,tmp=1;
fp(i,0,n-1) ans+=tmp,tmp*=m;
return ans;
}
il double calc2(re int m,re int n)
{
double ans=0,tmp=1;
fp(i,1,n) ans+=tmp,tmp=tmp*m/(m-i);
return ans;
}
int main()
{
while(scanf("%d",&T)!=EOF)
{
while(T--)
{
scanf("%d%d%d",&op,&m,&n);
if(!op) printf("%.6lf
",calc1(m,n));
else printf("%.6lf
",calc2(m,n));
}
}
return 0;
}