QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#768534#5089. 环覆盖NineSuns0 659ms372284kbC++14850b2024-11-21 11:57:522024-11-21 11:57:52

Judging History

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

  • [2024-11-21 11:57:52]
  • 评测
  • 测评结果:0
  • 用时:659ms
  • 内存:372284kb
  • [2024-11-21 11:57:52]
  • 提交

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++) {
		memset(g, 0, sizeof g); 
		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; 
			}
		}
		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: 0
Time Limit Exceeded

Test #1:

score: 5
Accepted
time: 385ms
memory: 372220kb

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: 659ms
memory: 372284kb

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: 0
Time Limit Exceeded

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:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

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%