QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#768536#5089. 环覆盖NineSuns5 729ms372380kbC++14841b2024-11-21 11:58:392024-11-21 11:58:39

Judging History

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

  • [2024-11-21 11:58:39]
  • 评测
  • 测评结果:5
  • 用时:729ms
  • 内存:372380kb
  • [2024-11-21 11:58:39]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
#define pb push_back

using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int N = 45, mod = 1e9+7; 
int n, m, d[N], f[N][1<<20], g[N][1<<20], v[N]; 

void solve () {
	cin >> n >> m; 
	for (int i = 1;i <= m;i++) {
		int x, y; cin >> x >> y; 
		v[i] = (1<<x-1)|(1<<y-1); 
	}
	f[0][0] = 1; 
	for (int i = 1;i <= m;i++) {
		for (int z = 0;z < i;z++) {
			for (int j = 0;j < (1<<n);j++) {
				(g[z+1][j^v[i]] += f[z][j]) %= mod; 
				(g[z][j] += f[z][j]) %= mod; 
				f[z][j] = 0; 
			}
		}
		swap(f, g); 
	}
	for (int i = 0;i <= m;i++) {
		int ans = 0; 
		cout << f[i][0] << " "; 
	}
}

signed main () {
	int T = 1; 
	while (T--) solve();
	return 0;
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 227ms
memory: 372296kb

input:

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

output:

1 0 0 1 1 1 0 0 0 0 

result:

ok 10 numbers

Test #2:

score: 5
Accepted
time: 377ms
memory: 372240kb

input:

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

output:

1 0 0 10 18 26 46 54 43 30 18 8 2 0 0 0 

result:

ok 16 numbers

Test #3:

score: 5
Accepted
time: 729ms
memory: 372172kb

input:

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

output:

1 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 

result:

ok 20 numbers

Test #4:

score: 5
Accepted
time: 368ms
memory: 372164kb

input:

7 14
1 3
1 4
1 7
2 3
2 5
2 6
2 7
3 4
3 5
3 7
4 7
5 6
5 7
6 7

output:

1 0 0 11 16 18 46 64 47 30 18 5 0 0 0 

result:

ok 15 numbers

Test #5:

score: 5
Accepted
time: 231ms
memory: 372380kb

input:

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

output:

1 0 0 0 0 1 0 0 0 0 

result:

ok 10 numbers

Test #6:

score: 5
Accepted
time: 369ms
memory: 372244kb

input:

15 14
2 9
2 10
3 5
3 10
3 12
3 14
4 6
5 10
5 15
6 9
6 15
7 11
7 13
9 15

output:

1 0 0 2 0 1 3 1 0 0 0 0 0 0 0 

result:

ok 15 numbers

Test #7:

score: 5
Accepted
time: 203ms
memory: 372304kb

input:

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

output:

1 0 0 0 0 0 0 0 0 

result:

ok 9 numbers

Test #8:

score: 5
Accepted
time: 685ms
memory: 372300kb

input:

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

output:

1 0 0 0 1 0 1 2 0 0 1 2 0 0 0 0 0 0 0 

result:

ok 19 numbers

Test #9:

score: 5
Accepted
time: 462ms
memory: 372176kb

input:

7 18
1 2
1 3
1 4
1 6
1 7
2 3
2 5
2 6
2 7
3 4
3 5
3 7
4 5
4 6
4 7
5 6
5 7
6 7

output:

1 0 0 20 51 108 278 528 711 760 660 468 293 156 54 8 0 0 0 

result:

ok 19 numbers

Test #10:

score: 5
Accepted
time: 381ms
memory: 372204kb

input:

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

output:

1 0 0 4 6 12 16 12 9 4 0 0 0 0 0 0 

result:

ok 16 numbers

Subtask #2:

score: 0
Time Limit Exceeded

Dependency #1:

100%
Accepted

Test #11:

score: 15
Accepted
time: 562ms
memory: 372204kb

input:

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

output:

1 0 0 13 33 64 162 367 621 906 1216 1343 1215 988 682 353 146 58 20 4 0 0 0 

result:

ok 23 numbers

Test #12:

score: 0
Time Limit Exceeded

input:

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

output:

1 0 0 50 210 800 3661 14805 51947 164232 466335 1177265 2639525 5274024 9420013 15077609 21687685 28100640 32827271 34579721 32851761 28140784 21708463 15062239 9394113 5261128 2639589 1183171 472151 166600 51607 13987 3278 656 117 17 1 0 0 

result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #31:

score: 0
Time Limit Exceeded

input:

25 45
1 6
1 12
1 17
2 3
2 4
2 6
3 6
3 8
4 5
4 12
4 16
5 17
6 21
7 14
7 22
7 23
8 15
8 19
8 24
9 11
9 19
9 23
9 25
10 17
10 18
11 16
11 19
11 22
12 19
13 18
14 19
15 19
16 24
17 19
17 22
17 25
18 19
18 21
18 24
19 23
20 22
21 25
22 23
23 25
24 25

output:


result:


Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%