QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #112884 | #6555. Sets May Be Good | vme50 | WA | 1ms | 3824kb | C++17 | 1.1kb | 2023-06-15 07:59:00 | 2023-06-15 07:59:02 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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'