HDU 4652 Dice（概率dp） - c++编程基础

Problem Description You have a dice with m faces, each face contains a distinct number. We assume when we tossing the dice, each face will occur randomly and uniformly. Now you have T query to answer, each query has one of the following form:
0 m n: ask for the expected number of tosses until the last n times results are all same.
1 m n: ask for the expected number of tosses until the last n consecutive results are pairwise different.
Input The first line contains a number T.(1≤T≤100) The next T line each line contains a query as we mentioned above. (1≤m,n≤10 ⁶) For second kind query, we guarantee n≤m. And in order to avoid potential precision issue, we guarantee the result for our query will not exceeding 10 ⁹ in this problem.
Output For each query, output the corresponding result. The answer will be considered correct if the absolute or relative error doesn't exceed 10 ^-6.
Sample Input

6
0 6 1
0 6 3
0 6 5
1 6 2
1 6 4
1 6 6
10
1 4534 25
1 1232 24
1 3213 15
1 4343 24
1 4343 9
1 65467 123
1 43434 100
1 34344 9
1 10001 15
1 1000000 2000

Sample Output

1.000000000
43.000000000
1555.000000000
2.200000000
7.600000000
83.200000000
25.586315824
26.015990037
15.176341160
24.541045769
9.027721917
127.908330426
103.975455253
9.003495515
15.056204472
4731.706620396

参考别人的博客：http://blog.csdn.net/auto_ac/article/details/9919851

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
            #define L(x) (x<<1) #define R(x) (x<<1|1) #define MID(x,y) ((x+y)>>1) #define eps 1e-8 typedef __int64 ll; #define fre(i,a,b) for(i = a; i 
            
             = a;i--) #define mem(t, v) memset ((t) , v, sizeof(t)) #define ssf(n) scanf("%s", n) #define sf(n) scanf("%d", &n) #define sff(a,b) scanf("%d %d", &a, &b) #define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c) #define pf printf #define bug pf("Hi\n") using namespace std; #define INF 0x3f3f3f3f #define N 10005 int n,m; double pp; void solve() { int i,j; double ans=0; fre(i,0,n) ans+=pow(pp,i); pf("%.7f\n",ans); } void solvee() { int i,j; double t=1; double ans=0; double up=m,down=m; double temp=up/down; fre(i,0,n) { ans+=temp; down--; temp*=up/down; } pf("%.7f\n",ans); } int main() { int i,j,t; while(~sf(t)) { int op; while(t--) { sfff(op,m,n); if(op==0) { pp=m; solve(); } else { solvee(); } } } return 0; }