らての精進日記

修行をします

Typical DP Contest D:サイコロ

解法

1~6の自然数をそれぞれ素因数分解すると、2と3と5だけが現れます。つまり、Dが2,3,5以外の素数を約数に含んでいたらアウトです。
Dが2,3,5の積の形で表せるときは、

dp[i][a][b][c]:i回サイコロを振って、素因数分解すると2がa回、3がb回,5がc回現れるような数になる確率

としました。

初めて解く感じの問題でした。

コード

#include<bits/stdc++.h>
using namespace std;
#define int long long

//            2    3   5
double dp[2][100][50][50];
int N,D;
signed main(){
    cin>>N>>D;
    int c2=0,c3=0,c5=0;
    while(D%2==0){D/=2;c2++;}
    while(D%3==0){D/=3;c3++;}
    while(D%5==0){D/=5;c5++;}

    if(D!=1){
        printf("%.10lf",0);
        return 0;
    }


    dp[0][0][0][0]=1;

    for(int i=0;i<N;i++){
        for(int pc2=0;pc2<=c2;pc2++)for(int pc3=0;pc3<=c3;pc3++)for(int pc5=0;pc5<=c5;pc5++){
            for(int j=1;j<=6;j++){
                int nc2=min(c2,(j==2||j==6?pc2+1:(j==4?pc2+2:pc2)));
                int nc3=min(c3,(j%3==0?pc3+1:pc3));
                int nc5=min(c5,(j%5==0?pc5+1:pc5));
                dp[(i+1)&1][nc2][nc3][nc5]+=dp[i&1][pc2][pc3][pc5]/6.0;
            }
            dp[i&1][pc2][pc3][pc5]=0;
        }
    }


    printf("%.10lf\n",dp[N&1][c2][c3][c5]);
    return 0;
}