oj.uz

Submission #19667

# Submission time Handle Problem Language Result Execution time Memory
19667 2016-02-25T04:24:09 Z myungwoo 악수 (kriii4_D) C++14
0 / 100
 0 ms 1720 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

const int MOD = 1e9+7;
int N;
int v[6][6], F[11];
lld sum, all;
bool V[6];

void ff(int n)
{
	V[n] = 1;
	for (int i=1;i<=N;i++) if (v[n][i] && !V[i]) ff(i);
}

bool is_con()
{
	for (int i=1;i<=N;i++) V[i] = 0;
	ff(1);
	for (int i=1;i<=N;i++) if (!V[i]) return 0;
	return 1;
}

void dfs(int left)
{
	int turn = N*(N-1)/2 - left;
	if (is_con()){
		sum += turn;
		all += F[left];
		return;
	}
	for (int i=1;i<=N;i++) for (int j=i+1;j<=N;j++) if (!v[i][j]){
		v[i][j] = v[j][i] = 1;
		dfs(left-1);
		v[i][j] = v[j][i] = 0;
	}
}

lld gcd(lld a, lld b){ return b ? gcd(b, a%b) : a; }

int rev(int n)
{
	int p = MOD-2, v = n, ret = 1;
	for (;p;p>>=1,v=(lld)v*v%MOD) if (p&1) ret = (lld)ret*v%MOD;
	return ret;
}

int main()
{
	F[0] = 1;
	for (int i=1;i<11;i++) F[i] = F[i-1] * i;
	scanf("%d", &N);
	assert(N <= 5);
	dfs(N*(N-1)/2);
	lld g = gcd(sum, all);
	sum /= g, all /= g;
	printf("%lld\n", (lld)sum%MOD*rev(all%MOD)%MOD);
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1720 KB Output is correct
2 Correct 0 ms 1720 KB Output is correct
3 Correct 0 ms 1720 KB Output is correct
4 Incorrect 0 ms 1720 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -