QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #418495 | #6555. Sets May Be Good | light_ink_dots | WA | 1ms | 3976kb | C++14 | 1.6kb | 2024-05-23 14:14:57 | 2024-05-23 14:14:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
static const long long mod = 998244353;
static const int maxn = 1010;
int n, m;
scanf("%d %d", &n, &m);
static bitset<maxn> A[maxn];
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
A[u].set(v);
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++)
if (A[i].test(j))
A[j].flip(i), A[i].reset(j);
int p = i + 1;
while (p <= n && !A[p].test(i)) p++;
if (p == n + 1)
continue;
if (p != i + 1) {
swap(A[i + 1], A[p]);
for (int j = i + 1; j <= n; j++) {
bool x = A[j][i + 1], y = A[j][p];
A[j].set(i + 1, y), A[j].set(j, x);
}
}
bitset<maxn> msk;
for (int j = i + 2; j <= n; j++)
if (A[j].test(i))
A[j] ^= A[i + 1], msk.set(j);
for (int j = i + 1; j <= n; j++)
if (A[j].test(i + 1))
A[j] ^= msk;
}
static long long dp[2][2];
dp[0][0] = dp[A[1].test(1)][1] = 1;
for (int i = 2; i <= n; i++) {
static long long nxt[2][2];
memset(nxt, 0, sizeof(nxt));
for (int s = 0; s < 2; s++)
for (int x = 0; x < 2; x++)
for (int y = 0; y < 2; y++)
nxt[s ^ (x && y && A[i].test(i - 1)) ^ (y && A[i].test(i))][y] += dp[s][x];
for (int s = 0; s < 2; s++)
for (int x = 0; x < 2; x++) dp[s][x] = nxt[s][x] % mod;
}
printf("%lld\n", (dp[0][0] + dp[0][1]) % mod);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3932kb
input:
5 5 1 2 2 3 3 4 4 5 1 5
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
3 0
output:
8
result:
ok 1 number(s): "8"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
2 1 1 2
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3976kb
input:
4 6 1 2 1 3 1 4 2 3 2 4 3 4
output:
6
result:
ok 1 number(s): "6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
1 0
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3976kb
input:
4 5 1 2 1 3 1 4 2 3 3 4
output:
8
result:
ok 1 number(s): "8"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
5 3 1 3 1 4 1 5
output:
24
result:
ok 1 number(s): "24"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
5 0
output:
32
result:
ok 1 number(s): "32"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
6 3 1 2 3 4 3 6
output:
40
result:
ok 1 number(s): "40"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
6 0
output:
64
result:
ok 1 number(s): "64"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3972kb
input:
7 3 2 3 3 6 6 7
output:
80
result:
ok 1 number(s): "80"
Test #12:
score: 0
Accepted
time: 1ms
memory: 3928kb
input:
7 0
output:
128
result:
ok 1 number(s): "128"
Test #13:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
20 30 1 7 1 9 1 12 1 13 2 6 2 17 3 13 4 12 4 15 4 17 6 10 6 17 7 8 7 18 8 14 9 13 10 16 10 17 12 14 13 15 13 16 13 20 14 16 14 18 14 20 15 17 15 18 15 19 15 20 16 17
output:
524288
result:
ok 1 number(s): "524288"
Test #14:
score: -100
Wrong Answer
time: 1ms
memory: 3964kb
input:
20 73 1 4 1 9 1 13 2 6 2 7 2 12 2 14 2 18 2 19 3 6 3 10 3 12 3 14 3 16 3 17 3 18 4 6 4 7 4 11 4 14 4 15 4 18 4 19 5 6 5 7 5 9 5 10 5 12 5 14 5 15 5 17 5 18 5 19 5 20 6 12 6 13 6 15 6 16 6 17 7 9 7 16 7 19 8 11 8 15 8 16 8 20 9 10 9 12 9 17 9 20 10 11 10 12 10 14 10 16 10 17 10 18 11 12 11 20 12 13 1...
output:
523776
result:
wrong answer 1st numbers differ - expected: '524288', found: '523776'