Submission #169217

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cassert>
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <iterator>
#include <queue>
#include <utility>

using namespace std;

int N;
vector< pair<int, int> > C;
#define whole(xs) xs.begin(), xs.end()

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        int c; cin >> c;
        C.push_back(make_pair(c, i));
    }
    sort(whole(C));
    int Count = 0;
    do {
        bool F[N]; memset(F, 1, sizeof(F));
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (C[j].first % C[i].first == 0) {
                    F[j] = !F[j];
                }
            }
        }
        for (int i = 0; i < N; i++) {
            Count += F[i];
        }
    } while (next_permutation(whole(C)));
    double Ans = Count;
    int Div = 1;
    for (int i = 1; i <= N; i++) {
        Div *= i;
    }
    printf("%.9f\n", Ans / Div);
    return 0;
}

Submission Info

Judge Result