QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#299212#5357. 芒果冰加了空气HMSF15 85ms200168kbC++142.2kb2024-01-06 17:48:532024-01-06 17:48:54

Judging History

你现在查看的是最新测评结果

  • [2024-01-06 17:48:54]
  • 评测
  • 测评结果:15
  • 用时:85ms
  • 内存:200168kb
  • [2024-01-06 17:48:53]
  • 提交

answer

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
//#include<vector>
//#include<set>
//#include<queue>
//#include<stack>
#define PII pair<int,int>
#define MP make_pair
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LDB;
inline LL read()
{
	LL s=0; bool w=0; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') w=1; ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}
	return w ? ~s+1 : s;
}

const int maxn = 5005;
const LL mod = 1000000007;

inline LL madd(LL a,LL b){a+=b; return a>=mod ? a-mod : a;}
inline LL msub(LL a,LL b){a-=b; return a<0    ? a+mod : a;}
inline LL M(LL a,LL b){return (a*b)%mod;}
LL qpow(LL bse,LL exp) {
	LL res = 1; while(exp) {
		if(exp&1){res = M(res,bse);}
		bse = M(bse,bse); exp>>=1;
	} return res;
}

LL jxig[maxn+10],jxiginv[maxn+10];
void init_math()
{
	jxig[0] = 1;
	for(int i=1; i<=maxn; i++) jxig[i] = M(jxig[i-1],i);
	jxiginv[maxn] = qpow(jxig[maxn],mod-2);
	for(int i=maxn-1; i>=0; i--) jxiginv[i] = M(jxiginv[i+1],i+1);
	return;
}
inline LL C(LL N,LL R){return N>=R ? M(jxig[N],M(jxiginv[R],jxiginv[N-R])) : 0;}

int n;
struct Edge { int v,nxt; }e[maxn<<1];
int h[maxn],ecnt;
void adde(int u,int v) { ecnt++; e[ecnt].v = v; e[ecnt].nxt = h[u]; h[u] = ecnt; return; }

LL f[maxn][maxn];
LL g[maxn];
int siz[maxn];

void DP(int u,int lst)
{
	siz[u] = 0;
	for(int i=0; i<=n; i++) g[i] = 0;
	f[u][0] = 1;
	for(int i=h[u]; i; i=e[i].nxt)
	{
		int v = e[i].v; if(v==lst) continue;
		DP(v,u);
		for(int j=siz[u]; j>=0; j--)
			for(int k=0; k<=siz[v]; k++)
				g[j+k] += M(M(f[v][k],f[u][j]),C(j+k,j));
		siz[u] += siz[v];
		for(int j=0; j<=siz[u]; j++) { f[u][j] = g[j]; g[j] = 0; }
	}
	siz[u]++;
	for(int i=siz[u]; i>=1; i--) { f[u][i] = f[u][i-1]; } f[u][0] = 0;
	for(int i=siz[u]-1; i>=0; i--) { f[u][i] = madd(f[u][i],f[u][i+1]); }
	return;
}

int main()
{
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	init_math();
	n = read();
	for(int i=1; i<n; i++)
	{
		int u = read(); int v =read();
		adde(u,v); adde(v,u);
	}
	DP(1,0);
	printf("%lld\n",f[1][0]);
	//fclose(stdin);fclose(stdout);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 1ms
memory: 3980kb

input:

10
1 2
2 3
3 4
5 4
6 4
7 4
8 4
9 4
10 4

output:

310862

result:

ok single line: '310862'

Test #2:

score: 0
Accepted
time: 1ms
memory: 5904kb

input:

10
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
8 10

output:

64804

result:

ok single line: '64804'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3984kb

input:

10
1 2
1 3
3 4
3 5
3 6
4 7
3 8
4 9
4 10

output:

258182

result:

ok single line: '258182'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

output:

16796

result:

ok single line: '16796'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3980kb

input:

10
1 2
2 3
3 4
4 5
1 6
2 7
3 8
4 9
5 10

output:

78384

result:

ok single line: '78384'

Test #6:

score: 0
Accepted
time: 1ms
memory: 5892kb

input:

10
1 2
1 3
2 4
3 5
2 6
4 7
3 8
7 9
9 10

output:

38896

result:

ok single line: '38896'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

10
1 2
2 3
4 3
5 3
6 3
7 3
8 3
9 3
10 3

output:

609656

result:

ok single line: '609656'

Test #8:

score: 0
Accepted
time: 1ms
memory: 5912kb

input:

10
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
9 10

output:

64804

result:

ok single line: '64804'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

10
1 2
1 3
3 4
3 5
1 6
4 7
1 8
4 9
9 10

output:

118638

result:

ok single line: '118638'

Test #10:

score: 0
Accepted
time: 1ms
memory: 5872kb

input:

10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
8 10

output:

22438

result:

ok single line: '22438'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

10
1 2
1 3
2 4
3 5
4 6
5 7
6 8
7 9
8 10

output:

16796

result:

ok single line: '16796'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

10
1 2
1 3
1 4
3 5
4 6
2 7
3 8
5 9
5 10

output:

82316

result:

ok single line: '82316'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

8
1 2
3 2
4 2
5 2
6 2
7 2
8 2

output:

13700

result:

ok single line: '13700'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

8
1 2
1 3
2 4
2 5
3 6
3 7
3 8

output:

3996

result:

ok single line: '3996'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

8
1 2
2 3
1 4
1 5
1 6
3 7
6 8

output:

3490

result:

ok single line: '3490'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3932kb

input:

8
1 2
2 3
3 4
4 5
5 6
6 7
7 8

output:

1430

result:

ok single line: '1430'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3988kb

input:

8
1 2
1 3
2 4
3 5
4 6
5 7
6 8

output:

1430

result:

ok single line: '1430'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

8
1 2
2 3
3 4
2 5
3 6
5 7
4 8

output:

3232

result:

ok single line: '3232'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

8
1 2
2 3
4 3
5 3
6 3
7 3
8 3

output:

8970

result:

ok single line: '8970'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

8
1 2
1 3
2 4
2 5
3 6
3 7
2 8

output:

3996

result:

ok single line: '3996'

Test #21:

score: 0
Accepted
time: 1ms
memory: 5852kb

input:

8
1 2
1 3
1 4
4 5
3 6
4 7
2 8

output:

3332

result:

ok single line: '3332'

Test #22:

score: 0
Accepted
time: 1ms
memory: 5804kb

input:

8
1 2
2 3
3 4
4 5
5 6
6 7
2 8

output:

1870

result:

ok single line: '1870'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

8
1 2
2 3
1 4
2 5
3 6
4 7
5 8

output:

2416

result:

ok single line: '2416'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

8
1 2
1 3
2 4
3 5
2 6
6 7
3 8

output:

2802

result:

ok single line: '2802'

Test #25:

score: 0
Accepted
time: 0ms
memory: 4020kb

input:

3
1 2
2 3

output:

5

result:

ok single line: '5'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

10
1 2
1 3
1 4
4 5
1 6
6 7
3 8
5 9
2 10

output:

78904

result:

ok single line: '78904'

Subtask #2:

score: 10
Accepted

Test #27:

score: 10
Accepted
time: 78ms
memory: 200168kb

input:

5000
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

138172849

result:

ok single line: '138172849'

Test #28:

score: 0
Accepted
time: 16ms
memory: 90476kb

input:

2195
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

34585647

result:

ok single line: '34585647'

Test #29:

score: 0
Accepted
time: 49ms
memory: 158524kb

input:

3927
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

179814607

result:

ok single line: '179814607'

Test #30:

score: 0
Accepted
time: 6ms
memory: 38796kb

input:

857
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
5...

output:

997745350

result:

ok single line: '997745350'

Test #31:

score: 0
Accepted
time: 4ms
memory: 49180kb

input:

1157
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

459486613

result:

ok single line: '459486613'

Test #32:

score: 0
Accepted
time: 85ms
memory: 200108kb

input:

4958
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

276300910

result:

ok single line: '276300910'

Test #33:

score: 0
Accepted
time: 28ms
memory: 113040kb

input:

2758
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

161112418

result:

ok single line: '161112418'

Test #34:

score: 0
Accepted
time: 26ms
memory: 117668kb

input:

2905
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

501208825

result:

ok single line: '501208825'

Test #35:

score: 0
Accepted
time: 16ms
memory: 84436kb

input:

2047
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

995483163

result:

ok single line: '995483163'

Test #36:

score: 0
Accepted
time: 32ms
memory: 125624kb

input:

3098
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 51
51 52
52 53
...

output:

324344238

result:

ok single line: '324344238'

Subtask #3:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #37:

score: 0
Wrong Answer
time: 0ms
memory: 3880kb

input:

20
1 2
2 3
3 4
1 5
3 6
5 7
5 8
8 9
7 10
10 11
9 12
12 13
10 14
11 15
13 16
16 17
17 18
18 19
16 20

output:

14085351596

result:

wrong answer 1st lines differ - expected: '85351498', found: '14085351596'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #5:

0%