AtCoder Beginner Contest 008 C - コイン

昔の ABC 難しくないですか…

問題

abc008.contest.atcoder.jp

解法

あるコイン C[i] が表を向く確率をそれぞれの i について求める, という方針で行きます。

C[i]%C[j] = 0 かつ i != j を満たす j の集合を S, S の大きさを cnt とします(つまり C[i] の約数の数)。すると, S のうちいくつの要素が C[i] より左側に来ているか, というので C[i] が表を向くか裏を向くかが決まります。表を向く確率が各 C[i] について高速で求まれば, その和を取ることにより答えが得られます(期待値の線形性)。

確率を求める際, S に含まれないものの並びについては関係がないので, cnt! 通りのコインの並びについてのみ考えれば良いです。

C[i] よりも左側に l 枚の約数があったとすると, その並び方の場合の数は, comb[n][r] を「n 個から r 個選ぶ場合の数」として,
comb[cnt][l] * l! * (cnt-l)! = cnt!
となります。つまり, 左に何枚あるかに関係なく, すべて同じ場合の数だけ並び方がある, ということなので, 結局確率は, 「0, 1, ..., cnt のうち, 偶数になるものはいくつあるか」というのが分かれば良いだけになります。

int main() {
    int N;
    cin >> N;
    vector<int> C(N);
    for (int i = 0; i < N; i++) cin >> C[i];
    double ans = 0;
    for (int i = 0; i < N; i++) {
        int cnt = 0;
        for (int j = 0; j < N; j++) if (i!=j) {
            if (C[i]%C[j] == 0) cnt++;
        }
        ans += 1.*(cnt/2+1)/(cnt+1);
    }
    printf("%.10lf\n", ans);
    return 0;
}