SRM730 div2 med ExpectedMinimumPowerDiv2

概要

1~nまでの数からx個をランダムに選ぶ。このとき選んだx個のうち最小のものをSとし2^Sをその集合のスコアとする。スコアの期待値を求めろ。

考えたこと

• 数mが最小の数Sになるのはどんなときか
• x個にmが含まれていてm未満の数が含まれていない
• したがってm以上の数であるn-m個の中からx-1個を選んだ時Sはmになる
• SがmになるのはC(n-m, x-1)通り
• n個からx個を選ぶのは全部でC(n,x)通りなので 2^S * C(n-m,x-1) / C(n,x) を求めればいい
• n,x<=50なのでパスカルの三角形でコンビネーションを求められる
• オーバーフローにだけ気をつけて計算する

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
const int INF = (1LL<<30);
const ll LLINF = (1LL<<60);
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;
//#define int ll

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

ll c[55][55] = {};
void init_comb(int n) {
  REP(i, n) {
    c[i][0] = c[i][i] = 1;
    FOR(j, 1, i) c[i][j] = c[i-1][j] + c[i-1][j-1];
  }
}
ll C(int n, int r) {
  return c[n][r];
}

class ExpectedMinimumPowerDiv2 {
   public:
   double findExp(int n, int x)
  {
    init_comb(n+5);
    double ret = 0;
    double all = C(n, x);
    cout << all << endl;
    FOR(i, 1, n+1) {
      ret += (1LL<<i) / all * C(n-i, x-1);
    }

    return ret;
  }
};