Submission #169710

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cstdio>
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();++i)

int n;
double nCr(int n, int r){
	if(n < r || r < 0) return 0.0;
	r = max(r, n-r);
	double sum = 1;
	for(int i=n;i>r;i--) sum *= i;
	for(int i=2;i<n-r;i++) sum /= i;
//	printf("%dC%d = %f\n", n, r, sum);
	return sum;
}
double nPr(int n, int r){
	if(n < r || r < 0) return 0.0;
	double sum = 1;
	for(int i=n;i>n-r;i--) sum *= i;
//	printf("%dP%d = %f\n", n, r, sum);
	return sum;
}

main(){
	cin >> n;
	vector<int> d(n), c(n);
	REP(i,n) cin >> d[i];
	REP(i, n) REP(j, n) if(i!=j && d[i] % d[j] == 0) c[i] ++;
	double sum = 0;
	REP(i, n) for(int j=0;j<n;j++){ //d[i] is j-th from left
		for(int k=0;k<=c[i]&&k<=j;k+=2){
			double ret = nPr(c[i], k) * nPr(n-1-c[i], j-k) * nCr(j, k) / nPr(n-1, j);
//			printf("%d %d %d %f\n", i, j, k, ret);
			if(ret > n) ret = n;
			ret /= n;
			sum += ret;
		}
	}
	printf("%.10f\n", sum);
	return 0;
}

Submission Info

Judge Result