Submission #169800

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, num;
vector<int> data;
int state[100 + 5];


int factorial( int n ){
    int f = 1;
    
    for (int i=1; i<=n ; i++ ){
        f *= i;
    }
    return f;
}

void check(int pos){
    for(unsigned int i = pos; i < data.size()-1; ++i){
        //cout << data[i+1] << " % " << data[pos] << "=" << data[i+1] % data[pos] << endl;
        if(data[i+1] % data[pos] == 0){
            if(state[i+1] == 1){
                state[i+1] = 0;
//                cout << "0 in" << state[i+1] << endl;
            }else{
                state[i+1] = 1;
                //cout << "1 in" << endl;
            }
        }
    }
}

int main(){
    int sum = 0;

    cin >> N;
    for(int i=0; i < N; i++){
        cin >> num;
        data.push_back(num);
    }

    int fac = factorial(N);

    // 全ての順列を出力
    do{
        for(int i = 0; i < 105; i++){
            state[i] = 1;
        }
        for(unsigned int i=0; i < data.size()-1; ++i){
/*
            for(int j = 0; j < N; j++){
                cout << data[j] << ",";
            }
            cout << endl;
            */
            check(i);
/*            
            for(int j = 0; j < N; j++){
                cout << state[j] << ",";
//                sum += state[j];
            }
            cout << endl;            
            */
        }
        //cout << "--- ";
        for(int j = 0; j < N; j++){
            //cout << state[j] << ",";
            sum += state[j];
        }
        //cout << endl;

    }while(next_permutation(data.begin(), data.end()));

    float res = (float)sum / fac;

    //cout << sum << ", " << fac << endl;

    cout << res << endl;


}

Submission Info

Judge Result