Typical DP Contest D - サイコロ

解法

サイコロの出た目の積の素因数には 2, 3, 5 しかない.
つまり,D にそれ以外の素因数があればダメ.
そうでなければ,D = 2^a * 3^b * 5^c と一意的に表すことができる.
dp[x][y][z] := 今現在,2の素因数が x 個,3 の素因数が y 個,5 の素因数が z 個となる確率
というDPテーブルを考えれば,そこからもう一つサイコロを投げた時の遷移が簡単に書ける.
計算量は O(Nabc) となる.
N <= 100 だが,a, b, c はもっと小さいので余裕で間に合う.(2 ^ 64 で 10^18 を超えてしまう)

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
    ll N, D;
    cin >> N >> D;
    int a[3] = {};
    int div[3] = {2, 3, 5};
    for(int i=0; i<3; ++i) {
        while(D % div[i] == 0) {
            a[i]++;
            D /= div[i];
        }
    }
    if(D > 1) {
        cout << 0 << endl;
        return 0;
    }
    vector<vector<vector<double>>> dp(a[0]+1, vector<vector<double>>(a[1]+1, vector<double>(a[2]+1)));
    dp[0][0][0] = 1;
    constexpr int dx[6] = {0, 1, 0, 2, 0, 1};
    constexpr int dy[6] = {0, 0, 1, 0, 0, 1};
    constexpr int dz[6] = {0, 0, 0, 0, 1, 0};
    for(int i=0; i<N; ++i) {
        vector<vector<vector<double>>> next(a[0]+1, vector<vector<double>>(a[1]+1, vector<double>(a[2]+1)));
        for(int x=0; x<=a[0]; ++x) {
            for(int y=0; y<=a[1]; ++y) {
                for(int z=0; z<=a[2]; ++z) {
                    for(int l=0; l<6; ++l) {
                        int nx = min(a[0], x+dx[l]);
                        int ny = min(a[1], y+dy[l]);
                        int nz = min(a[2], z+dz[l]);
                        next[nx][ny][nz] += dp[x][y][z] / 6.0;
                    }
                }
            }
        }
        dp.swap(next);
    }
    cout << fixed << setprecision(10) << dp[a[0]][a[1]][a[2]] << endl;
}