Typical DP Contest D - サイコロ

問題文 : サイコロ

解法 :

$dp[i][j][k] := 2^i3^j5^k$ が出来る確率として$N$ 回dp テーブルを回していく.
ここで, 2, 3, 5 以外の素因数が含まれていればその数が出来ないことに注意する.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>

using namespace std;

double dp[2][70][70][70];

int main()
{
	int N;
	int count[6] = {0};
	long long int D;
	
	scanf("%d %lld", &N, &D);
	
	while (D % 2 == 0) {count[2]++; D /= 2;}
	while (D % 3 == 0) {count[3]++; D /= 3;}
	while (D % 5 == 0) {count[5]++; D /= 5;}
	
	if (D != 1) return (!printf("0\n"));
	
	for (int i = 0; i < 2; i++)
		for (int j = 0; j < 70; j++)
			for (int k = 0; k < 70; k++)
				for (int l = 0; l < 70; l++)
					dp[i][j][k][l] = 0;
	
	dp[0][0][0][0] = 1;
	for (int i = 1; i <= N; i++){
		for (int j = 0; j <= 67; j++) for (int k = 0; k <= 67; k++) for (int l = 0; l <= 67; l++){
			dp[i & 1][j][k][l] = 0;
		}
		
		for (int j = 0; j <= count[2]; j++) for (int k = 0; k <= count[3]; k++) for (int l = 0; l <= count[5]; l++){
			double p = 1 / 6.0;
			dp[i & 1][j][k][l] += p * dp[(i - 1) & 1][j][k][l];
			dp[i & 1][min(count[2], j + 1)][k][l] += p * dp[(i - 1) & 1][j][k][l];
			dp[i & 1][j][min(count[3], k + 1)][l] += p * dp[(i - 1) & 1][j][k][l];
			dp[i & 1][min(count[2], j + 2)][k][l] += p * dp[(i - 1) & 1][j][k][l];
			dp[i & 1][j][k][min(count[5], l + 1)] += p * dp[(i - 1) & 1][j][k][l];
			dp[i & 1][min(count[2], j + 1)][min(count[3], k + 1)][l] += p * dp[(i - 1) & 1][j][k][l];
		}
	}
	
	double ans = 0;
	for (int i = count[2]; i <= 67; i++) for (int j = count[3]; j <= 67; j++) for (int k = count[5]; k <= 67; k++){
		ans += dp[N & 1][i][j][k];
	}
	
	printf("%.9lf\n", ans);
	
	return (0);
}