ABC 8 C - コイン ( Expectation )

C: コイン - AtCoder Beginner Contest 008 | AtCoder
Problem statement: Given some coins and their value, initially they are in any random permutation, all heads facing up. You will flip each coin from left to right, and every time a coin is flipped, all the coins with a value that is multiple of the currently flipped coin will be flipped as well. What is the expectation of the number of heads of the coins facing up after all the operations?
We can simply examine for each coins, for its expectation to be head facing up in the end and sum it up. For each coin, let the number of other coins with a value that is a factor of it be cnt. If cnt is odd, there are cnt + 1 spaces which this coin could be possibly placed in, each with the same probability, and ( cnt + 1 ) / 2, half of the possible places will make this coin be in the even position, which means this coin has 50% having its head facing up in the end. Otherwise if cnt is even, there are cnt + 1 spaces, and only cnt / 2 + 1 of them will place this coin in a position that will have its head facing up in the end.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;
 
int n;
int c[ MAXN ];
 
void solve(){
    double ans = 0.0;
    for(int i = 0; i < n; ++i){
        int cnt = 0;
        for(int j = 0; j < n; ++j) if( i != j )
            cnt += ( c[ i ] % c[ j ] == 0 );
        if( cnt & 1 ) ans += 0.5;
        else ans += (double)( cnt / 2 + 1 ) / ( cnt + 1 );
    }
    printf("%.7lf\n", ans);
}
 
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        cin >> c[ i ];
    solve();
    return 0;
}