Submission #18999

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
18999	2016-02-17T02:52:07 Z	kriii	악수 (kriii4_D)	C++14	5 / 100	262 ms	2888 KB

D

#include <stdio.h>

const long long mod = 1000000007;
long long inv[450],comb[450][450],end[31][450],all[31][450];

int main()
{
	int n,m; scanf ("%d",&n);
	comb[0][0] = comb[1][0] = comb[1][1] = inv[1] = 1;
	for (int i=2;i<450;i++){
		comb[i][0] = comb[i][i] = 1;
		for (int j=1;j<i;j++) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % mod;
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	}

	end[1][0] = all[1][0] = 1;
	for (int v=2;v<=n;v++){
		int l = v * (v - 1) / 2;
		for (int e=v-1;e<=l;e++){
			for (int i=0;i<v-1;i++) for (int j=0;j<e;j++){
				long long add = comb[v-1][i] * comb[e-1][j] % mod;
				add = add * all[i+1][j] % mod;
				add = add * all[v-i-1][e-j-1] % mod;
				add = add * (i + 1) * (v - i - 1) % mod;
				end[v][e] += add;
			}
			end[v][e] %= mod;
			all[v][e] = (end[v][e] + (l - e + 1) * all[v][e-1]) % mod;
		}
	}

	long long coeff = 1, ans = 0;
	m = n * (n - 1) / 2;
	for (int i=1;i<=m;i++){
		coeff = coeff * inv[m-i+1] % mod;
		ans = (ans + end[n][i] * coeff % mod * i) % mod;
	}
	printf ("%lld\n",ans);

	return 0;
}

Subtask #1

5.0 / 5.0

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

Subtask #2

0.0 / 95.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	2888 KB	Output is correct
2	Correct	0 ms	2888 KB	Output is correct
3	Correct	1 ms	2888 KB	Output is correct
4	Correct	0 ms	2888 KB	Output is correct
5	Correct	0 ms	2888 KB	Output is correct
6	Correct	0 ms	2888 KB	Output is correct
7	Correct	0 ms	2888 KB	Output is correct
8	Correct	0 ms	2888 KB	Output is correct
9	Correct	3 ms	2888 KB	Output is correct
10	Correct	4 ms	2888 KB	Output is correct
11	Correct	3 ms	2888 KB	Output is correct
12	Correct	8 ms	2888 KB	Output is correct
13	Correct	11 ms	2888 KB	Output is correct
14	Correct	15 ms	2888 KB	Output is correct
15	Correct	20 ms	2888 KB	Output is correct
16	Correct	27 ms	2888 KB	Output is correct
17	Correct	35 ms	2888 KB	Output is correct
18	Correct	45 ms	2888 KB	Output is correct
19	Correct	58 ms	2888 KB	Output is correct
20	Correct	74 ms	2888 KB	Output is correct
21	Correct	94 ms	2888 KB	Output is correct
22	Correct	114 ms	2888 KB	Output is correct
23	Correct	143 ms	2888 KB	Output is correct
24	Correct	176 ms	2888 KB	Output is correct
25	Correct	220 ms	2888 KB	Output is correct
26	Runtime error	262 ms	2884 KB	SIGSEGV Segmentation fault
27	Halted	0 ms	0 KB	-