結果
問題 | No.574 正多面体サイコロ |
ユーザー |
|
提出日時 | 2017-10-07 16:19:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,706 bytes |
コンパイル時間 | 1,906 ms |
コンパイル使用メモリ | 169,476 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-17 04:30:09 |
合計ジャッジ時間 | 2,478 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<double> calc_fac(int N){ vector<double> fac(N + 1, 1.0); for (int i = 1; i <= N; ++i) fac[i] = fac[i - 1] * i; return fac; } vector<double> calc_p(double p, int N){ vector<double> ps(N + 1, 1.0); for (int i = 0; i < N; ++i) ps[i + 1] = ps[i] * p; return ps; } double prob(int x, int F, int N, int K, const vector<double> & pM, const vector<double> & fac){ // F面体をN回振って、K番目に大きい数字がxである確率 // x+1以上の数字が出た回数が L回で、x-1以下の数字が出た回数がS回、xと等しい値が出た回数はM = N - L - S 回とする。 // このとき、x が K番目に大きい数字となるためには、L, S が以下を満たすことが必要。 // 0 <= L < K, and K <= N - S and S >= 0 // 0 <= L < K and 0 <= S <= N - K // このような目の出方が生じる確率は、 // p(L, S) = ((F - x)/F)^L * ((x - 1)/F)^S * (1/F)^M * N!/(L! * S! * M!) auto pL = calc_p((F - x)*1.0/F, K); auto pS = calc_p((x - 1)*1.0/F, N - K + 1); double ret = 0.0; for (int L = 0; L < K; ++L){ for (int S = 0; S <= N - K; ++S){ int M = N - L - S; ret += pL[L] * pS[S] * pM[M] * fac[N] / fac[L] / fac[S] / fac[M]; } } return ret; } double solve(int F, int N, int K){ double ans = 0.0; auto pM = calc_p(1.0/F, N); auto fac = calc_fac(N); for (int x = 1; x <= F; ++x){ ans += x * prob(x, F, N, K, pM, fac); } return ans; } int main() { int F, N, K; cin >> F >> N >> K; cout.precision(12); cout << fixed << solve(F, N, K) << endl; return 0; }