Typical DP Contest D サイコロ

方針

与えられたnを素因数分解する。
7以上の素因数が含まれていたら無理が確定する。


dp[サイコロを振った個数][2の指数][3の指数][5の指数] := それになる確率
として、更新していくDPをすればいい。

ソースコード

long double dp[2][201][101][101]; //2, 3, 5

int main(){
	ll n, d;
	int cur = 0, next = 1;
	cin >> n >> d;
	
	dp[0][0][0][0] = 1;
	rep(i, n){
		memset(dp[next], 0, sizeof(dp[next]));
		rep(j, 2*i+1) rep(k, i+1) rep(l, i+1) if(dp[cur][j][k][l]){
			
			dp[next][j][k][l] += dp[cur][j][k][l]; //1
			dp[next][j+1][k][l] += dp[cur][j][k][l]; //2
			dp[next][j][k+1][l] += dp[cur][j][k][l]; //3
			dp[next][j+2][k][l] += dp[cur][j][k][l]; //4
			dp[next][j][k][l+1] += dp[cur][j][k][l]; //5
			dp[next][j+1][k+1][l] += dp[cur][j][k][l]; //6
		}
		swap(cur, next);
	}
	
	long double ans = 0;
	int two = 0, three = 0, five = 0;
	while(d % 2 == 0) two++, d /= 2;
	while(d % 3 == 0) three++, d /= 3;
	while(d % 5 == 0) five++, d /= 5;
	
	for(int i = two; i < 201; i++) for(int j = three; j < 101; j++) for(int k = five; k < 101; k++)
	ans += dp[cur][i][j][k];
	rep(i, n) ans /= 6.0;
	printf("%.9f\n", (double)ans * (d == 1));
	
	return 0;
}