Quiz
https://tdpc.contest.atcoder.jp/tasks/tdpc_dice
AC
https://tdpc.contest.atcoder.jp/submissions/8804908
テクい点
- サイコロN回分のdpテーブルを用意するとメモリが足りないので、2回分だけ用意して使い回す
- cur, next
- memset
- 素因数分解がsqrt(D)では間に合わない
- 2, 3, 5で割れるかだけ知りたいのでlog(D)で求められる
- dpテーブルはlong longで持つとオーバーフローするのでdoubleで持つ
- ちなみに最初はlong doubleとしていて、どちらでも通った
- doubleの方が2倍速かった(定数倍効く)
- dpテーブルの状態の持ち方
- dp[i][2の指数][3の指数][5の指数]
Code
double dp[2][201][101][101]; int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N, D; cin >> N >> D; ll cur = 0; ll next = 1; dp[0][0][0][0] = 1; rep(i, N){ memset(dp[next], 0, sizeof(dp[next])); // i回目なら、今までに出た2の数は ll num2_max = 2*i; ll num3_max = i; ll num5_max = i; rep(j, num2_max+1){ rep(k, num3_max+1){ rep(l, num5_max+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); // cur == 1 // next == 0 } ll d = D; 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; double sum = 0; FOR(i, two, 201){ FOR(j, three, 101){ FOR(k, five, 101){ sum += dp[cur][i][j][k]; } } } rep(i, N){ sum /= 6.0; } cout << setprecision(20); p(sum * (d==1)); return 0; }