HDU4652Dice(확률 DP)

제목 링크: 전송문
제목:
m면의 주사위를 정한 다음에 두 가지 질문을 한다. 0mn은 몇 번을 잃어버리면 마지막에 잃어버린 n번이 똑같은 기대를 가지게 되고, 1mn은 마지막에 잃어버린 n번이 똑같은 기대를 가지게 된다.
분석:
dp[i]를 설정하면 이미 i개의 동일/같지 않은 n개의 다른 기대가 있음을 나타낸다. 그러면 dp[n]는 분명히 0과 같다.
n개 연속 동일:
dp[0]= 1+dp[1], 0의 후계 상태는 1만 나타날 수 있고 확률은 1이다.
dp[1]=1+dp[2]*(1/m)+dp[1]*(m-1)/m, 1의 후계 상태는 1,2 두 가지 상황의 확률이 각각 (m-1)/m, 1/m일 뿐이다.
...
dp[i]=1+dp[i+1]*(1/m)+dp[1]*(m-1)/m, i의 후계 상태도 1에 불과하고 i+1 두 가지 상황의 확률은 각각(m-1)/m, 1/m이다.
dp[i+1]=1+dp[i+2]*(1/m)+dp[1]*(m-1)/m, i의 후계 상태도 1에 불과하고 i+2 두 가지 상황의 확률은 각각(m-1)/m, 1/m이다.
...
dp[n] = 0;
d[i]=dp[i]-dp[i+1], d[0]=1을 설정합니다.
d[i] = 1/m * d[i+1]
d[0]+d[1]+...+d[n-1] =  dp[0] - dp[n] = m^0 + m^1 +...+ m^(n-1) 
n개 연속:
dp[0]=1+dp[1] 0의 후계 상태는 1일 확률이 1이다.
dp[1] = 1 + dp[1]*(1/m) + dp[2]*(m-1)/m; 1의 후계 상태는 1,2이고 이 두 가지 상황의 확률은 1/m,(m-1)/m이다.
dp[2] = 1 + (dp[1]+dp[2])*(1/m) + dp[3]*(m-2)/m;1의 후계 상태는 1,2,3 이 세 가지 상황의 확률은 1/m, 1/m, (m-2)/m이다.
...
dp[i] = 1 + (dp[1] + dp[2]+...+ dp[i])*(1/m) + dp[i+1]*(m-i)/m;1의 후계 상태는 1, 2, 3,...i,i+1 이 i+1종의 상황 확률은 1/m,,,1/m,(m-i)/m;
dp[i+1] = 1 + (dp[1] + dp[2]+...+ dp[i]+dp[i+1])*(1/m) + dp[i+2]*(m-i-1)/m;1의 후계 상태는 1, 2, 3,...i,i+1 이 i+1종의 상황 확률은 1/m,,,1/m,(m-i-1)/m;
...
dp[n]=0;
d[i] = dp[i]-dp[i+1] = (m-i-1)/m*(dp[i+1]-dp[i+2)d[0]=1을 설정합니다.
dp[0] + dp[n] =  d[0] +d[2] +...+d[n-1] = m/(m-0) +m/(m-1)+...+m/(m-n+1)+m/(m-n);
코드는 다음과 같습니다.

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

double calc1(int m,int n){
    double ans = 0;
    for(int i=0;i<n;i++){
        ans = ans+pow(m+0.0,i);
    }
    return ans;
}

double calc2(int m,int n){
    double ans = 0;
    double tmp = 1.0;
    for(int i=1;i<=n;i++){
        ans+=tmp;
        tmp=tmp*m/(m-i);
    }
    return ans;
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int ord,n,m;
        scanf("%d%d%d",&ord,&m,&n);
        if(ord==0){
            printf("%.7lf
",calc1(m,n));
        }
        else{
            printf("%.7lf
",calc2(m,n));
        }
    }
    return 0;
}