Typical DP Contest D : サイコロ

問題リンク : D: サイコロ - Typical DP Contest | AtCoder

解法 :
Dを素因数分解したとき、その素因数に２、３、５以外のものが存在するのであれば求める確率は０となる
（サイコロの目が１から６までしかないので、例えば７は２、３、５の積ではどうやっても作れない）
それ以外の場合については、次のようなdp配列を用意し解を求める
dp[i][j][k][l] := i回さいころを振ったとき、素因数として２がj個、３がk個、５がl個となるような確率
また、愚直に配列を確保できないため、i,j,kがそれぞれ対応する素因数の数以上になったのであれば、その素因数の数にまとめる

コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
const int MAX = 75;
double dp[101][MAX][MAX][MAX];
//                      2              3              5 
int N,factor[3][6] = {{0,1,0,2,0,1},{0,0,1,0,0,1},{0,0,0,0,1,0}};//1,2,3,4,5,6
ll D;

map<ll,int> prime_factor(ll n) {
  map<ll,int> res;
  for(ll i=2;i*i<=n;i++) {
    while(n % i == 0) {
      ++res[i];
      n /= i;
    }
  }
  if(n != 1)res[n] = 1;
  return res;
}

int main() {
  cin >> N >> D;
  int a_2 = 0, a_3 = 0, a_5 = 0;
  map<ll,int> pf = prime_factor(D);
  for(map<ll,int>::iterator it=pf.begin();it!=pf.end();it++) {
    if( it->first != 2LL && it->first != 3LL && it->first != 5LL ) {
      puts("0.0000000000");
      return 0;
    }
    if( it->first == 2LL ) a_2 = it->second;
    if( it->first == 3LL ) a_3 = it->second;
    if( it->first == 5LL ) a_5 = it->second;
  }

  dp[0][0][0][0] = 1;
  rep(i,N) rep(_2,a_2+1) rep(_3,a_3+1) rep(_5,a_5+1) if( !equals(dp[i][_2][_3][_5],0) ) {
    rep(dice,6) {
      int n_2 = _2 + factor[0][dice], n_3 = _3 + factor[1][dice], n_5 = _5 + factor[2][dice];
      dp[i+1][min(a_2,n_2)][min(a_3,n_3)][min(a_5,n_5)] += dp[i][_2][_3][_5] / 6.0;
    }
  }

  printf("%.10f\n",dp[N][a_2][a_3][a_5]);
  return 0;
}