kojingharangの日記

Typical DP contest D サイコロ

01:54 |

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

• 倍数ということで素因数分解した形で考える
• サイコロの目 1〜6 は全て 2^i * 3^j * 5^k の形で表せる。
• だからなんなのさ

• シャワー浴びてたらひらめく !
• D に 7 以上の素因数があったらサイコロを何回振っても D の倍数にはならない ... ので 0 を印字して終わる
• D = 2^p2 * 3^p3 * 5^p5 と表せたので、なんか途中の状態を 2^? * 3^? * 5^? と表しておくんじゃないか
• dp[2の指数][3の指数][5の指数] = n回目にそういう状態になる確率
• 初期値は dp[0][0][0] = 1. 他の要素は 0
• サイを降るごとに状態全てについて目で場合分けして確率を更新. 3が出たら 2^0 * 3^1 * 5^0 掛けるので [i][j+1][k]のとこを更新　みたいな。
• 最終的に i ≧ p2 && j ≧ p3 && k ≧ p5 の確率を全部たしたものが答え。

• TLE
• コンテスト終了

(あとで)

• DP表の無駄なコピーを消す && dp[i][j][k]==0 ならスキップ
• accepted in practice

double dp[2][210][110][110];

int main() {
	//ios::sync_with_stdio(false);
	ll N, D;
	int tb[]={
		0, 0, 0,
		1, 0, 0,
		0, 1, 0,
		2, 0, 0,
		0, 0, 1,
		1, 1, 0,
	};
	while(cin>>N>>D) {
		int p2=0, p3=0, p5=0;
		while(D%2==0) p2++,D/=2;
		while(D%3==0) p3++,D/=3;
		while(D%5==0) p5++,D/=5;
		if(D>1) {
			cout<<0<<endl;
			continue;
		}
//		cout<<p2<<" "<<p3<<" "<<p5<<endl;
		int men=0;
		REP(m, 2) REP(i, 210) REP(j, 110) REP(k, 110) dp[m][i][j][k]=0;
		dp[men][0][0][0] = 1;
		REP(I, N) {
			REP(i, 210) REP(j, 110) REP(k, 110) {
				if(dp[men][i][j][k]==0.0) continue;
				REP(me, 6) {
					int ni = i+tb[me*3+0];
					int nj = j+tb[me*3+1];
					int nk = k+tb[me*3+2];
					if(ni<210 && nj<110 && nk<110) dp[1-men][ni][nj][nk] += dp[men][i][j][k] / 6.0;
				}
			}
			REP(i, 210) REP(j, 110) REP(k, 110) dp[men][i][j][k]=0;
			men ^= 1;
//			PRINT3(dp, 5, 5, 1);
		}
		double ans = 0;
		REP(i, 210) REP(j, 110) REP(k, 110) if(i>=p2 && j>=p3 && k>=p5) ans += dp[men][i][j][k];
		
		cout<<ans<<endl;
	}
	
	return 0;
}

ツイートする