Submission #1444674

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
#define LL long long

using namespace std;






int main(){

    int N;
    cin>>N;
    LL D;
    cin>>D;

    long double pro[3][3]={{1.0/2 , 1.0/3, 1.0/6},
                                 {2.0/3, 1.0/3, 0},
                                 {5.0/6, 1.0/6, 0}};

    int num[3];//(0,1,2) →(2,3,5) の出た回数…
    while(true){
        if(D%2!=0||D==0)break;
        num[0]++;
        D/=2;
    }
    while(true){
        if(D%3!=0||D==0)break;
        num[1]++;
        D/=3;
    }
    while(true){
        if(D%5!=0||D==0)break;
        num[2]++;
        D/=5;
    }

    if(D==0){
        cout<<0<<endl;
    }else{
        long double dp[3][N+1][201];
        fill(dp[0][0],dp[3][0],0);
        dp[0][0][0]=1;
        dp[1][0][0]=1;
        dp[2][0][0]=1;

        REP(k,3) {
            REP(i, N) {
                REP(j,201){
                    if(j==0)dp[k][i+1][j]=dp[k][i][j]*pro[k][0];
                    else if(j==1)dp[k][i+1][j]=dp[k][i][j]*pro[k][0]+dp[k][i][j-1]*pro[k][1];
                    else dp[k][i+1][j]=dp[k][i][j]*pro[k][0]+dp[k][i][j-1]*pro[k][1]+dp[k][i][j-2]*pro[k][2];
                }
            }
        }

        long double sigma[3]={0};
        REP(k,3){
            for (int j=num[k];j<201;j++){
                sigma[k]+=dp[k][N][j];
            }
        }

        cout<<fixed<<setprecision(10)<<sigma[0]*sigma[1]*sigma[2]<<endl;

    }

    return 0;
}

Submission Info

Judge Result