QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#352339 | #6555. Sets May Be Good | wangzhifang | WA | 0ms | 3952kb | C++14 | 1.3kb | 2024-03-13 09:58:58 | 2024-03-13 09:58:58 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int mod=998244353;
void modp(int&x){
x>=mod&&(x-=mod);
}
constexpr int max_n=1000;
bitset<max_n>f[max_n];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=m,u,v; i; --i,f[u-1].flip(v-1))
scanf("%d%d",&u,&v);
for(int i=0; i<n; ++i){
const int p=i+1;
for(int j=p; j<n; ++j)
if(f[i].test(j))
f[j].flip(i),f[i].reset(j);
int j=p;
for(; j<n; ++j)
if(f[j].test(i))
break;
if(j!=p){
swap(f[p],f[j]);
for(int k=i+1,p=i+1; k<n; ++k){
const bool x=f[k].test(j);
f[k].set(j,f[k].test(p));
f[k].set(p,x);
}
}
bitset<max_n>tmp;
while(++j<n)
if(f[j].test(i))
f[j]^=f[p],tmp.set(j);
for(int j=p; j<n; ++j)
if(f[j].test(p))
f[j]^=tmp;
}
int dp[2][2]={{1,0},{1,0}};
if(f[0].test(0))
dp[1][0]=0,dp[1][1]=1;
for(int i=1; i<n; ++i){
const int va=dp[0][0],vb=dp[0][1];
const bool ta=f[i].test(i);
const bool tb=ta^f[i].test(i-1);
modp(dp[0][0]+=dp[1][0]);
modp(dp[0][1]+=dp[1][1]);
if(tb)
swap(dp[1][0],dp[1][1]);
if(ta)
modp(dp[1][0]+=vb),modp(dp[1][1]+=va);
else
modp(dp[1][0]+=va),modp(dp[1][1]+=vb);
}
int ans=dp[0][0]+dp[1][0];
modp(ans);
printf("%d\n",ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
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: 3924kb
input:
3 0
output:
8
result:
ok 1 number(s): "8"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
2 1 1 2
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3764kb
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: 3760kb
input:
1 0
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3900kb
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: 0ms
memory: 3900kb
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: 3952kb
input:
5 0
output:
32
result:
ok 1 number(s): "32"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3808kb
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: 3884kb
input:
6 0
output:
64
result:
ok 1 number(s): "64"
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3948kb
input:
7 3 2 3 3 6 6 7
output:
96
result:
wrong answer 1st numbers differ - expected: '80', found: '96'