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;

template<typename T>
std::vector<T> table(int n, T v) { return std::vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return std::vector<decltype(val)>(n, std::move(val));
}

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};

int main() {
    cout << fixed << setprecision(10);

    ll n, d; cin >> n >> d;

    vector<int> cnt;
    for(auto const v : {2, 3, 5}) {
        int c = 0;
        while(d % v == 0) {
            d /= v;
            ++c;
        }
        cnt.push_back(c);
    }
    if(d != 1) {
        cout << 0 << endl;
        return 0;
    }

    auto dp = table(cnt[0] + 1, cnt[1] + 1, cnt[2] + 1, 0.0);
    dp[0][0][0] = 1;
    for(int lp = 0; lp < n; ++lp) {
        auto nxt = table(cnt[0] + 1, cnt[1] + 1, cnt[2] + 1, 0.0);
        for(int x = 0; x <= cnt[0]; ++x) {
            for(int y = 0; y <= cnt[1]; ++y) {
                for(int z = 0; z <= cnt[2]; ++z) {
                    for(int i = 0; i < 6; ++i) {
                        const int nx = min(cnt[0], x + dx[i]);
                        const int ny = min(cnt[1], y + dy[i]);
                        const int nz = min(cnt[2], z + dz[i]);
                        nxt[nx][ny][nz] += dp[x][y][z] / 6;
                    }
                }
            }
        }
        dp = move(nxt);
    }

    cout << dp[cnt[0]][cnt[1]][cnt[2]] << endl;
}