题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4652
题意：
给你一个有m个面的骰子。
两种询问：
（1）"0 m n": “最后n次点数均相同”的投掷次数期望。
（2）"1 m n": “最后n次点数各不相同”的投掷次数期望。
题解：
表示状态：
dp[i] = expectation （当前已经有i个点数相同/不相同）
找出答案：
ans = dp[0]
如何转移：
一、都相同
（1）dp[i] = dp[i+1]/m + dp[1]*(1-1/m) + 1 （要么与前面相同，要么不同）
（2）dp[i+1] = dp[i+2]/m + dp[1]*(1-1/m) + 1 （为了错位相减消去后面的dp[1]，令i = i+1）
（1）-（2）得：
dp[i] - dp[i+1] = (dp[i+1] - dp[i+2])/m
设d[i] = dp[i] - dp[i+1]，有d[i+1]= dp[i]*m （d[i]可递推）
则：dp[0] - dp[n] = sigma(d[0 to n-1]) （前后两项相消）
又因为：dp[n] = 0
所以：dp[0] = sigma(d[0 to n-1])，枚举求和即可。
二、都不同
（1）dp[i] = dp[i+1]*(m-i)/m + dp[i]/m + dp[i-1]/m +...+ dp[1]/m + 1 （要么与之前均不同，要么与第n,n-1,n-2...1位相同）
（2）dp[i+1] = dp[i+2]*(m-i-1)/m + dp[i+1]/m + dp[i]/m +...+ dp[1]/m + 1 （令i = i+1，错位相减）
（1）-（2）得：
dp[i] - dp[i+1] = (dp[i+1] - dp[i+2])*(m-i-1)/m
设d[i] = dp[i] - dp[i+1]，有d[i+1]= dp[i]*m/(m-i-1) （d[i]可递推）
则：dp[0] - dp[n] = sigma(d[0 to n-1])
同一中：dp[0] = sigma(d[0 to n-1]) 即为答案。
AC Code:
// PROB 1: is the same
//
// state expresssion:
// dp[i] = expectation
// i: the same numbers
//
// find the answer:
// ans = dp[1] + 1
//
// transferring:
// dp[i] = dp[i+1]/m + dp[1]*(1-1/m) + 1
// dp[i+1] = dp[i+2]/m + dp[1]*(1-1/m) + 1
// dp[i] - dp[i+1] = dp[i+1]/m - dp[i+2]/m
// dp[i] - dp[i+1] = (dp[i+1] - dp[i+2])/m
// dp[i+1] - dp[i+2] = (dp[i] - dp[i+1])*m
// d[0] = dp[0] - dp[1] = 1
// dp[0] + dp[n] = sigma(d[0 to n-1])
// dp[0] = sigma(d[0 to n-1])
//
//
// PROB 2: is different
//
// state expression:
// dp[i] = expectation
// i: different numbers
//
// find the answer:
// ans = dp[1] + 1
//
// transferring:
// dp[i] = dp[i+1]*(m-i)/m + dp[i]/m + dp[i-1]/m +...+ dp[1]/m + 1
// dp[i+1] = dp[i+2]*(m-i-1)/m + dp[i+1]/m + dp[i]/m +...+ dp[2]/m + dp[1]/m + 1
// dp[i] - dp[i+1] = dp[i+1]*(m-i)/m - dp[i+2]*(m-i-1)/m - dp[i+1]/m
// dp[i] - dp[i+1] = (dp[i+1] - dp[i+2])*(m-i-1)/m
// dp[i+1] - dp[i+2] = (dp[i] - dp[i+1])*m/(m-i-1)
// d[0] = dp[0] - dp[1] = 1
// dp[0] + dp[n] = sigma(d[0 to n-1])
// dp[0] = sigma(d[0 to n-1])
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1000005 using namespace std; int n,m,p,t;
double ans;
double dp[MAX_N]; void read()
{
cin>>p>>m>>n;
} void cal_dp_same()
{
// dp[i+1] - dp[i+2] = (dp[i] - dp[i+1])*m
// dp[0] = sigma(d[0 to n-1])
double d=;
ans=;
for(int i=;i<n;i++)
{
ans+=d;
d*=m;
}
} void cal_dp_dif()
{
// dp[i+1] - dp[i+2] = (dp[i] - dp[i+1])*m/(m-i-1)
// dp[0] = sigma(d[0 to n-1])
double d=;
ans=;
for(int i=;i<n;i++)
{
ans+=d;
d*=m/(m-i-1.0);
}
} void solve()
{
if(p==) cal_dp_same();
else cal_dp_dif();
} void print()
{
printf("%.9f\n",ans);
} int main()
{
while(cin>>t)
{
while(t--)
{
read();
solve();
print();
}
}
}
dp[i] = dp[i+1]*(m-i)/m + dp[i]/m + dp[i-1]/m +...+ dp[1]/m + 1