oj.uz

Submission #19674

# Submission time Handle Problem Language Result Execution time Memory
19674 2016-02-25T04:26:29 Z myungwoo 악수 (kriii4_D) C++14
5 / 100
 6 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*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);
	all = F[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
5.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 Correct 0 ms 1720 KB Output is correct
5 Correct 6 ms 1720 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1720 KB gettid (syscall #186) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -