QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#119785#6555. Sets May Be Good5abWA 61ms7476kbC++141.6kb2023-07-05 19:17:502023-07-05 19:17:50

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-05 19:17:50]
  • 评测
  • 测评结果:WA
  • 用时:61ms
  • 内存:7476kb
  • [2023-07-05 19:17:50]
  • 提交

answer

/* name: 6555
 * author: 5ab
 * created at: 2023-07-05
 */
#include <iostream>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

using ll = long long;
const int max_n = 1000, mod = 998244353;

int g[max_n][max_n];
bool chk[max_n];

ll qpow(int n)
{
	ll ans = 1, mul = 2;
	while (n)
	{
		if (n & 1)
			ans = ans * mul % mod;
		mul = mul * mul % mod;
		n >>= 1;
	}
	return ans;
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	
	cin >> n >> m;
	for (int i = 0, x, y; i < m; i++)
	{
		cin >> x >> y, x--, y--;
		if (x > y) swap(x, y);
		g[x][y] = 1;
	}
	
	int frc = 0, cf = 0;
	for (int i = 0; i < n; i++)
		if (!chk[i])
		{
			int fst = -1;
			for (int j = i + 1; j < n; j++)
				if (g[i][j])
				{
					fst = j;
					break;
				}
			if (fst == -1)
			{
				if (g[i][i] == 1)
				{
					frc = 0;
					break;
				}
				frc++;
				continue;
			}
			frc++;
			chk[fst] = true;
			if (g[i][i])
			{
				cf ^= g[fst][fst];
				for (int j = fst + 1; j < n; j++)
					g[j][j] ^= g[fst][j];
			}
			for (int j = i + 1; j < n; j++)
				if (j < fst ? g[j][fst] : g[fst][j])
				{
					(j < fst ? g[j][fst] : g[fst][j]) = 0;
					for (int k = fst + 1; k < n; k++)
						(j < k ? g[j][k] : g[k][j]) ^= g[i][k];
				}
		}
	if (frc == 0)
		cout << qpow(n - 1);
	else if (cf == 0)
		cout << (qpow(n - 1) + qpow(frc - 1)) % mod;
	else
		cout << (qpow(n - 1) - qpow(frc - 1) + mod) % mod;
	cout << endl;
	
	return 0;
}
// started coding at: 07-05 18:33:18

详细

Test #1:

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

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: 3492kb

input:

3 0

output:

8

result:

ok 1 number(s): "8"

Test #3:

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

input:

2 1
1 2

output:

3

result:

ok 1 number(s): "3"

Test #4:

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

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: 3428kb

input:

1 0

output:

2

result:

ok 1 number(s): "2"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3576kb

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: 3400kb

input:

5 3
1 3
1 4
1 5

output:

24

result:

ok 1 number(s): "24"

Test #8:

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

input:

5 0

output:

32

result:

ok 1 number(s): "32"

Test #9:

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

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: 3396kb

input:

6 0

output:

64

result:

ok 1 number(s): "64"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3404kb

input:

7 3
2 3
3 6
6 7

output:

80

result:

ok 1 number(s): "80"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3424kb

input:

7 0

output:

128

result:

ok 1 number(s): "128"

Test #13:

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

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: 0
Accepted
time: 1ms
memory: 3404kb

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:

524288

result:

ok 1 number(s): "524288"

Test #15:

score: 0
Accepted
time: 61ms
memory: 7476kb

input:

1000 499500
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1...

output:

818794637

result:

ok 1 number(s): "818794637"

Test #16:

score: -100
Wrong Answer
time: 23ms
memory: 7476kb

input:

1000 10000
1 14
1 53
1 132
1 139
1 174
1 237
1 246
1 278
1 302
1 349
1 353
1 396
1 465
1 652
1 698
1 706
1 753
1 845
1 848
1 862
1 884
1 911
1 1000
2 31
2 57
2 80
2 118
2 182
2 195
2 198
2 344
2 347
2 585
2 591
2 597
2 611
2 623
2 642
2 672
2 694
2 704
2 731
2 770
2 852
2 923
2 974
3 8
3 12
3 59
3 8...

output:

510735315

result:

wrong answer 1st numbers differ - expected: '128609606', found: '510735315'