TypicalDP Contest D - サイコロ

問題文
サイコロを N 回振ったとき、出た目の積が D の倍数となる確率を求めよ。
1≤N≤100
1≤D≤10^18

解説
https://github.com/osak/Contest/tree/master/AtCoder/TypicalDP
を見てから自分で書いてみた。

サイコロによってできる積の素因数の種類は 2, 3, 5 に限られる。それ以外の素因数を持つ D が与えられたとき、その倍数が生じる確率は 0 である。

サイコロの 4 の目では素因数 2 を 2個持つが、他の目では素因数 2, 3, 5 に対してそれぞれ高々 1 個ずつしか持たない。よって出来る積の値の素因数は 2 は高々 200 個持ち、3, 5 は高々 100 個持つ。

よって素因数の個数で DP するとよい。

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;

int N; ll D;
double prob[2][210][110][110];
int TWO, THREE, FIVE;

int const Dice[6][3] = {
  {0, 0, 0},
  {1, 0, 0},
  {0, 1, 0},
  {2, 0, 0},
  {0, 0, 1},
  {1, 1, 0}
};

int main() {
  
  cin >> N >> D;
  
  while(D % 2 == 0) TWO ++, D /= 2;
  while(D % 3 == 0) THREE ++, D /= 3;
  while(D % 5 == 0) FIVE ++, D /= 5;
  
  if(D != 1) {
    cout << 0 << endl;
    return 0;
  }
  
  for(int i=0; i<6; i++) {
    prob[1][ Dice[i][0] ][ Dice[i][1] ][ Dice[i][2] ] = 1./6.;
  }
  
  for(int n=1; n<N; n++) {
    for(int i=0; i<201; i++) {
      for(int j=0; j<101; j++) {
        for(int k=0; k<101; k++) {
          if(prob[n&1][i][j][k] == 0.) continue;  // これがないと TLE する
          for(int d=0; d<6; d++) {
            int ni = i+Dice[d][0];
            int nj = j+Dice[d][1];
            int nk = k+Dice[d][2];
            prob[(n+1)&1][ni][nj][nk] += prob[n&1][i][j][k] / 6.;
          }
          prob[n&1][i][j][k] = 0.;
        }
      }
    }
  }
  
  double ret = 0.;
  for(int i=TWO; i<201; i++)
    for(int j=THREE; j<101; j++)
      for(int k=FIVE; k<101; k++)
        ret += prob[N&1][i][j][k];
  
  printf("%.7f\n", ret);
  
  return 0;
}