Submission #169626

---

Source Code Expand

#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;

#define NUM 100

int N;
double count_ = 0;
vector<int> coin_number;
vector<int> array;

// 再帰関数で並べて、その時の表の数を求める
// nは入れるのが何個目の数字かについての数
void get_count(int n);

int main(void) {
    cin >> N;
    array.reserve(N);
    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        coin_number.push_back(tmp);
    }
    get_count(0);
    for (int i = 1; i <= N; i++) {
        count_ /= i;
    }
    cout << count_ << endl;
    return 0;
}

void get_count(int n) {
    if (n == N) {
        // 表の数を求める
        vector<bool> omote(N);
        vector<int> array2(N);
        for (int i = 0; i < N; i++) {
            omote[i] = true;
            array2[i] = coin_number[array[i]];
        }
        for (int i = 0; i < N; i++) {
            for (int j = i+1; j < N; j++) {
                if (array2[j] % array2[i] == 0) omote[j] = !omote[j];
            }
        }
        int countcount = 0;
        for (int i = 0; i < N; i++) {
            if (omote[i]) countcount++;
        }
        count_ += countcount;
        return;
    }
    int x, i; //候補
    for (int x = 0; x < coin_number.size(); x++) {
        for (i = 0; i < n; i++) {
            if (array[i] == x) break;
        }
        if (i == n) {
            array[n] = x;
            get_count(n+1);
        }
    }
    return;
}

Submission Info

Judge Result