QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#112884#6555. Sets May Be Goodvme50WA 1ms3824kbC++171.1kb2023-06-15 07:59:002023-06-15 07:59:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-15 07:59:02]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3824kb
  • [2023-06-15 07:59:00]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define N 1005
#define MOD 998244353
int n,m,o1=1,o2,pw[N];bool a[N][N];
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
int add(int x,int y) {x+=y;return x<MOD?x:x-MOD;}
int main()
{
	scanf("%d %d",&n,&m);pw[0]=1;
	for(int i=1;i<=n;++i) pw[i]=add(pw[i-1],pw[i-1]);
	for(int i=1,u,v;i<=m;++i) scanf("%d %d",&u,&v),a[u][v]^=1;
	while(n)
	{
		int u=0;for(int i=1;i<n;++i) if(a[i][n]) {u=i;break;}
		if(!u)
		{
			if(a[n][n]) o2=(o2+1ll*o1*pw[n-1])%MOD,o1=0;
			else o1=add(o1,o1),o2=add(o2,o2);--n;continue;
		}
		for(int i=u+1;i<n;++i)
		{
			for(int j=1;j<=n;++j) a[i][j]^=a[u][j];
			for(int j=1;j<=n;++j) a[j][i]^=a[j][u];
		}
		for(int i=1;i<=n;++i) for(int j=1;j<i;++j)
			a[j][i]^=a[i][j],a[i][j]=0;
		if(a[n][n])
		{
			if(a[u][u]) o2=(o2+3ll*o1*pw[n-2])%MOD,o1=add(-add(o1,o1),MOD);
			else o2=(o2+1ll*o1*pw[n-2])%MOD,o1=add(o1,o1);
			for(int i=1;i<=n;++i) if(a[u][i] || a[i][u]) a[i][i]^=1;
		}else o2=(o2+1ll*o1*pw[n-2])%MOD,o1=add(o1,o1);
		for(int i=1;i<n;++i) if(i!=u) for(int j=i;j<n;++j) if(j!=u)
			a[i-(i>u)][j-(j>u)]=a[i][j];n-=2;
	}printf("%d\n",add(o1,o2));return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3648kb

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: 1ms
memory: 3708kb

input:

3 0

output:

8

result:

ok 1 number(s): "8"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

2 1
1 2

output:

3

result:

ok 1 number(s): "3"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3636kb

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: 1ms
memory: 3648kb

input:

1 0

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3584kb

input:

4 5
1 2
1 3
1 4
2 3
3 4

output:

6

result:

wrong answer 1st numbers differ - expected: '8', found: '6'