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