Quiz
https://atcoder.jp/contests/abc011/tasks/abc011_4
Submit
https://atcoder.jp/contests/abc011/submissions/4062978
その他
- パスカルの三角形でnCrを事前計算
- nCrで持つと1000_C_500等の時に10300くらいの値になってWAになる
- long doubleで持っても収まったように見えてWAになる
- editorialにある通り、パスカルの三角形を確率バージョンにして保持してから求めたらAC 101点となった
Code
const int N_MAX = 1001; double pascal[N_MAX][N_MAX] = {}; // パスカルの三角形 // 確率Ver // n段目は 2^n で割った値が入る (横の和 = 1) void calc_pascal(){ FOR(i, 0, N_MAX){ pascal[i][0] = 1.0 / pow(2.0f, i); } pascal[1][1] = 1.0/2.0; FOR(i, 2, N_MAX){ for(int j=1; j<=i; j++){ pascal[i][j] = pascal[i-1][j] + pascal[i-1][j-1]; pascal[i][j] /= 2.0; } } }