QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#768534 | #5089. 环覆盖 | NineSuns | 0 | 659ms | 372284kb | C++14 | 850b | 2024-11-21 11:57:52 | 2024-11-21 11:57:52 |
Judging History
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%