Submission #19667

#	Time	Username	Problem	Language	Result	Execution time	Memory
19667		myungwoo	악수 (kriii4_D)	C++14	0 / 100	0 ms	1720 KiB

D

#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 / 5
• Subtask 2: 0 / 95