#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class TripleCardComplete { public: // // カード枚数が 0 枚, 1 枚, 2 枚のカードの種類数を状態としてもつ DP でやる // // +-> Exp[a][b][c] -a のうちどれかが出る-> Exp[a-1][b+1][c] // | | | // | | +-------b のうちどれかが出る-> Exp[a][b-1][c+1] // +----+ | // +-------c のうちどれかが出る-> Exp[a][b][c-1] // int N; // 時間・空間計算量 O(10^6) double memo[101][101][101]; // カード枚数が 0 枚のものが a 種類残っている // カード枚数が 1 枚のものが b 種類残っている // カード枚数が 2 枚のものが c 種類残っている // ときからスタートしたときのカードをコンプリートするまで買うカードの期待値 double calc(int a, int b, int c) { if (memo[a][b][c] >= 0) // すでに計算済み return memo[a][b][c]; double res = 0.0; int total = a+b+c; if (total == 0) // 全て手に入った return memo[a][b][c] = 0.0; // a,b,c に含まれるカードたちのどれかが出る確率 double p = (double)total/N; double q = 1.0/p; // 結局自分自身から他へ遷移しないケース // a,b,c に含まれるカードたちが出る確率は p だった。 // これら以外が出るまでの試行回数の期待値は 1/p なのでこれを加える。 res += q; // 自己ループを複数回くりかえしてから別状態への遷移がある場合もあるので q 掛ける if (a) res += calc(a-1,b+1,c) * (double)a/N * q; // a のうちどれかが出るときの遷移 if (b) res += calc(a,b-1,c+1) * (double)b/N * q; // b のうちどれかが出るときの遷移 if (c) res += calc(a,b,c-1) * (double)c/N * q; // c のうちどれかが出るときの遷移 return memo[a][b][c] = res; } void solve(void) { cin>>N; vector A(N); REP(i,101) REP(j,101) REP(k,101) memo[i][j][k] = -1; int n[3] = {0,0,0}; // n[i] := はじめに持っているカード枚数が i 枚のカードの種類総数 REP(i,N) { cin>>A[i]; if (A[i] < 3) ++n[A[i]]; } cout<solve(); delete obj; return 0; } #endif