QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#352339#6555. Sets May Be GoodwangzhifangWA 0ms3952kbC++141.3kb2024-03-13 09:58:582024-03-13 09:58:58

Judging History

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

  • [2024-03-13 09:58:58]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3952kb
  • [2024-03-13 09:58:58]
  • 提交

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'