Submission #19012

#	Time	Username	Problem	Language	Result	Execution time	Memory
19012		kriii	악수 (kriii4_D)	C++14	5 / 100	3000 ms	1084 KiB

D

#include <stdio.h>
#include <algorithm>

const long long mod = 1000000007;
long long inv[16],sum;

int main()
{
	int n; scanf ("%d",&n);
	inv[1] = 1;
	for (int i=2;i<=15;i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;

	int x[15],y[15],p[15],c=0;
	for (int i=0;i<n;i++) for (int j=i+1;j<n;j++) x[c] = i, y[c] = j, p[c] = c, c++;

	do{
		int par[10];
		for (int i=0;i<n;i++) par[i] = i;
		int con = n;
		for (int j=0;j<c;j++){
			int a = par[x[p[j]]], b = par[y[p[j]]];
			if (a != b){
				for (int i=0;i<n;i++) if (par[i] == b) par[i] = a;
				if (--con == 1){
					sum += j + 1;
					break;
				}
			}
		}
	}while (std::next_permutation(p,p+c));

	for (int i=1;i<=c;i++) sum = sum * inv[i] % mod;
	printf ("%lld\n",sum);

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 95