思路：
dp[i]表示当前在已经投掷出i个不相同/相同这个状态时期望还需要投掷多少次
对于第一种情况有：
dp[0] = 1+dp[1]
dp[1] = 1+((m-1)*dp[1]+dp[2])/m
dp[i] = 1+((m-1)*dp[1]+dp[i+1])/m
……
dp[n] = 0
可以得到：dp[n-1]=m*dp[n]+1
所以dp[0]=(m^n-1)/(m-1)也即是第一种的答案！
对于第二种情况有：
dp[0]=1+dp[1]
dp[1]=1+(dp[1]+(m-1)*dp[2])/m
dp[i]=1+(dp[1]+……+dp[i]+(m-i)*dp[i+1])/m
……
dp[n]=0
令d[i]=dp[i]-dp[i+1]
则有d[i]=m*dp[i-1]/(m-i),d[0]=1
所以dp[0]=∑d[i]也即是第二种的答案！！
代码如下：
#include<stdio.h>
#include<cmath>
double sum,d;
int pows(int a,int b){
int ans=;
while(b){
if(b&) ans*=a;
b>>=;
a*=a;
}
return ans;
}
int main(){
int q,n,m,i,j,t;
while(scanf("%d",&t)!=EOF){
for(i=;i<t;i++){
scanf("%d%d%d",&q,&m,&n);
if(q==) printf("%.9lf\n",(pows(m,n)-1.0)/(m-1.0));
else{
sum=d=1.0;
for(j=;j<n;j++){
d=1.0*m/(m-j)*d;
sum+=d;
}
printf("%.9lf\n",sum);
}
}
}
return ;
}