oj.uz

Submission #19012

# Submission time Handle Problem Language Result Execution time Memory
19012 2016-02-17T03:19:36 Z kriii 악수 (kriii4_D) C++14
5 / 100
 3000 ms 1084 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1084 KB Output is correct
2 Correct 0 ms 1084 KB Output is correct
3 Correct 0 ms 1084 KB Output is correct
4 Correct 0 ms 1084 KB Output is correct
5 Correct 166 ms 1084 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3000 ms 1080 KB Program timed out
2 Halted 0 ms 0 KB -