QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#423344#8729. TikvaniCrysfly78 49ms5036kbC++173.1kb2024-05-27 22:28:002024-05-27 22:28:00

Judging History

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

  • [2024-05-27 22:28:00]
  • 评测
  • 测评结果：78
  • 用时：49ms
  • 内存：5036kb
查看
  • [2024-05-27 22:28:00]
  • 提交

answer

// what is matter? never mind. 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
#define ull unsigned long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define mod 1000000007
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,modint b){return a.x==b.x;}
	friend bool operator !=(modint a,modint b){return a.x!=b.x;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 505
#define inf 0x3f3f3f3f

int n,m,e[maxn][maxn];
int id[maxn][maxn],tot;

typedef bitset<maxn> bint;
struct bas{
	int cnt;
	bint t[maxn];
	void ins(bint x){
		Rep(i,tot,1)
			if(x[i]){
				if(!t[i][i]) return t[i]=x,++cnt,void();
				x^=t[i];
			}
	}
}B;

signed main()
{
	n=read(),m=read();
	For(i,1,m){
		int u=read(),v=read();
		e[u][v]=1;
	}
	For(k,1,n)For(i,1,n)For(j,1,n)e[i][j]|=e[i][k]&e[k][j];
	For(i,1,n)For(j,i+1,n)if(e[i][j])id[i][j]=++tot;
	For(i,1,n)
		For(j,i+1,n)
			For(k,j+1,n)
				if(e[i][j] && e[j][k]){
					bint tmp;
					tmp[id[i][j]]=tmp[id[j][k]]=tmp[id[i][k]]=1;
					B.ins(tmp);
				}
				//	id[i][j]^id[j][k]^id[i][k]=0
	int res=tot-B.cnt;
	cout<<qpow(2,res).x;
	return 0;
}
/*
6 7
2 5
2 3
3 6
2 4
1 4
1 6
1 5
*/
源文件, 语言: C++17

详细

Subtask #1:

score: 21
Accepted

Test #1:

score: 21
Accepted
time: 0ms
memory: 3744kb

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #2:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #3:

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

input:

6 7
3 6
1 3
3 5
2 3
1 6
2 6
2 5

output:

16

result:

ok 1 number(s): "16"

Test #4:

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

input:

6 8
1 4
2 3
5 6
3 6
4 5
2 6
4 6
1 5

output:

32

result:

ok 1 number(s): "32"

Test #5:

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

input:

6 7
1 4
3 6
2 3
1 5
2 4
2 6
5 6

output:

64

result:

ok 1 number(s): "64"

Test #6:

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

input:

6 8
2 3
2 4
2 5
3 6
1 6
1 2
1 4
1 5

output:

32

result:

ok 1 number(s): "32"

Test #7:

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

input:

6 7
5 6
2 5
2 4
1 6
2 3
3 6
1 2

output:

32

result:

ok 1 number(s): "32"

Test #8:

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

input:

6 8
2 3
1 4
2 4
3 6
1 5
5 6
1 6
2 6

output:

64

result:

ok 1 number(s): "64"

Test #9:

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

input:

6 7
2 6
4 5
1 2
3 6
3 5
1 4
5 6

output:

32

result:

ok 1 number(s): "32"

Test #10:

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

input:

6 8
2 3
3 4
1 5
2 4
1 4
1 3
3 5
5 6

output:

32

result:

ok 1 number(s): "32"

Test #11:

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

input:

6 7
2 6
4 5
1 2
5 6
2 4
1 5
2 5

output:

16

result:

ok 1 number(s): "16"

Test #12:

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

input:

6 8
1 6
4 5
1 3
1 2
3 6
4 6
1 4
3 4

output:

32

result:

ok 1 number(s): "32"

Test #13:

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

input:

6 15
1 5
2 5
3 4
4 5
2 4
2 6
1 4
1 3
4 6
5 6
1 2
1 6
3 5
2 3
3 6

output:

32

result:

ok 1 number(s): "32"

Subtask #2:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #14:

score: 20
Accepted
time: 0ms
memory: 3680kb

input:

13 12
4 10
1 11
6 10
1 7
3 6
3 8
4 12
5 9
1 5
6 11
10 11
6 12

output:

2048

result:

ok 1 number(s): "2048"

Test #15:

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

input:

13 13
6 12
1 2
5 10
5 6
1 3
3 10
3 12
7 8
4 12
1 6
3 7
3 9
7 13

output:

4096

result:

ok 1 number(s): "4096"

Test #16:

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

input:

13 14
1 10
2 8
4 12
5 6
5 13
10 11
10 12
2 11
3 6
4 7
1 8
3 12
3 5
3 11

output:

8192

result:

ok 1 number(s): "8192"

Test #17:

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

input:

13 15
4 11
2 8
2 5
3 6
9 10
3 10
2 11
10 12
8 11
5 11
4 10
1 4
8 10
7 9
3 11

output:

8192

result:

ok 1 number(s): "8192"

Test #18:

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

input:

13 16
2 10
9 11
6 13
5 11
11 12
5 6
4 5
3 7
5 10
8 11
9 10
1 3
5 8
1 10
3 12
3 10

output:

16384

result:

ok 1 number(s): "16384"

Test #19:

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

input:

13 17
10 13
9 12
1 9
2 3
8 11
9 10
3 10
2 7
3 6
5 12
1 6
2 4
1 7
2 5
3 9
5 8
2 9

output:

16384

result:

ok 1 number(s): "16384"

Test #20:

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

input:

13 18
7 10
6 10
3 8
4 8
5 6
4 13
1 5
5 9
1 6
3 9
2 12
4 9
3 4
1 12
10 11
5 11
3 7
6 8

output:

16384

result:

ok 1 number(s): "16384"

Test #21:

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

input:

13 20
5 13
2 13
4 6
1 12
10 12
1 8
2 8
7 13
1 5
1 6
6 12
8 10
7 11
3 5
3 10
5 10
1 13
4 11
6 10
8 13

output:

4096

result:

ok 1 number(s): "4096"

Test #22:

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

input:

13 25
5 10
2 11
1 3
4 13
9 13
6 11
8 13
1 4
2 9
4 5
3 4
5 6
2 12
8 12
2 4
6 13
3 7
4 7
5 7
11 12
5 13
3 13
12 13
1 2
4 12

output:

4096

result:

ok 1 number(s): "4096"

Test #23:

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

input:

13 50
2 3
3 4
1 2
2 11
1 7
6 13
2 7
3 7
8 12
1 9
12 13
4 10
7 11
3 9
1 4
7 13
6 9
5 9
1 12
3 11
6 12
1 3
3 13
8 11
2 13
10 13
1 13
8 9
7 12
3 10
8 10
2 8
4 5
5 8
7 9
5 7
6 11
4 9
3 6
4 7
2 4
6 7
7 10
6 10
5 13
8 13
10 12
1 11
4 6
7 8

output:

4096

result:

ok 1 number(s): "4096"

Test #24:

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

input:

13 78
6 12
8 12
4 6
7 12
2 13
8 9
6 13
5 9
4 5
1 6
8 13
1 10
2 12
1 9
2 7
4 10
4 13
4 11
5 8
1 3
9 12
1 5
3 7
3 11
5 13
2 9
9 13
1 4
1 8
6 10
2 11
10 13
3 6
8 10
11 12
9 11
9 10
6 8
1 7
5 6
4 7
10 12
5 11
2 10
6 9
4 12
2 8
4 9
3 12
11 13
7 11
3 5
6 11
1 13
3 8
8 11
1 11
2 6
5 7
6 7
7 9
1 12
2 3
7 13...

output:

4096

result:

ok 1 number(s): "4096"

Subtask #3:

score: 37
Accepted

Test #25:

score: 37
Accepted
time: 1ms
memory: 3720kb

input:

50 50
29 32
3 12
36 41
10 30
6 18
20 27
14 36
4 33
6 7
17 31
33 40
2 49
19 42
3 30
2 18
11 42
21 29
11 23
1 35
32 50
22 46
6 22
42 48
15 23
7 43
11 13
5 9
40 50
25 42
5 31
27 30
1 17
14 48
5 44
35 41
1 23
10 21
40 48
12 36
13 37
23 37
23 43
19 26
6 15
13 45
19 27
17 29
20 38
29 42
26 49

output:

974740338

result:

ok 1 number(s): "974740338"

Test #26:

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

input:

49 50
23 42
22 30
8 18
28 42
14 37
34 40
11 34
2 5
9 14
24 34
11 32
41 45
8 28
6 23
9 17
22 31
20 38
4 47
2 39
13 22
14 26
8 45
37 45
17 23
34 37
13 37
33 48
5 12
17 37
27 30
17 21
18 22
28 43
10 23
33 43
31 49
10 43
8 26
12 19
14 28
6 14
2 20
12 49
26 39
35 45
14 48
3 6
14 36
6 48
1 17

output:

743685088

result:

ok 1 number(s): "743685088"

Test #27:

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

input:

48 50
4 39
3 43
41 47
10 34
19 36
5 17
19 35
34 38
5 30
32 47
10 41
3 44
11 29
13 37
5 47
18 33
1 45
29 45
2 13
2 38
8 36
3 34
40 45
8 20
4 21
4 31
18 43
29 32
26 38
13 29
35 48
10 36
1 9
14 23
13 34
16 27
5 18
16 36
1 6
1 36
36 44
39 43
21 39
30 42
11 18
5 11
9 37
15 30
25 45
29 40

output:

371842544

result:

ok 1 number(s): "371842544"

Test #28:

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

input:

47 50
16 21
23 44
12 42
8 25
5 19
29 37
11 27
14 20
18 44
46 47
8 42
20 29
1 29
19 31
2 33
16 27
13 39
37 40
12 18
3 37
2 43
35 43
19 22
3 44
19 32
42 46
29 33
1 4
3 18
7 38
2 40
4 26
16 31
28 45
20 34
12 15
5 17
14 41
13 20
25 41
6 15
31 33
24 35
13 33
7 11
12 16
2 31
35 44
10 25
17 47

output:

487370169

result:

ok 1 number(s): "487370169"

Test #29:

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

input:

46 50
1 35
27 34
2 46
18 23
7 45
17 28
12 38
6 17
38 42
15 46
1 29
11 14
12 27
4 39
37 38
25 30
2 42
22 23
13 27
7 15
30 33
19 27
27 36
26 42
20 42
25 37
27 33
30 38
16 32
5 33
17 34
12 31
35 40
15 39
40 44
10 38
19 41
24 36
38 46
19 29
19 35
8 28
12 45
27 40
22 40
8 27
16 19
10 22
12 20
17 35

output:

487370169

result:

ok 1 number(s): "487370169"

Test #30:

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

input:

45 50
38 45
29 43
24 38
1 44
16 22
13 21
3 7
35 45
22 33
27 38
11 26
29 32
3 15
34 36
17 34
14 33
29 35
12 13
11 18
15 41
5 45
20 41
12 27
21 39
15 34
33 42
32 42
13 44
25 37
3 4
14 25
28 34
7 14
4 41
9 27
23 35
39 45
6 29
26 30
10 35
18 43
4 12
2 9
23 40
3 40
16 43
2 28
27 45
4 35
14 35

output:

371842544

result:

ok 1 number(s): "371842544"

Test #31:

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

input:

40 50
6 8
10 13
6 40
37 38
27 30
15 34
1 13
18 32
24 40
3 25
11 35
30 35
6 26
33 35
3 26
34 35
2 32
19 32
9 25
8 14
8 12
1 6
6 38
9 34
21 32
6 21
13 14
2 12
24 25
10 21
9 35
19 33
7 26
13 17
14 19
8 16
14 23
34 40
2 25
2 33
16 37
6 14
1 14
25 30
13 31
23 24
3 18
15 20
24 30
9 26

output:

877905026

result:

ok 1 number(s): "877905026"

Test #32:

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

input:

30 50
4 11
18 25
17 22
4 28
8 15
11 26
2 25
2 4
12 21
20 26
6 30
4 21
15 18
25 28
13 16
27 28
18 22
21 25
13 27
23 26
24 30
6 26
3 24
1 4
7 30
1 5
6 12
10 19
1 6
11 29
14 18
1 14
1 25
12 20
9 28
12 16
10 28
18 28
3 26
11 13
15 25
4 13
7 18
28 30
7 28
19 25
14 28
3 15
8 19
6 13

output:

73741817

result:

ok 1 number(s): "73741817"

Test #33:

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

input:

20 50
8 17
1 12
4 11
1 8
7 13
5 19
9 20
4 5
2 12
1 7
5 18
8 12
6 12
6 7
10 18
14 17
2 13
4 18
12 15
3 8
3 5
6 13
5 14
6 8
4 8
7 17
9 15
11 15
13 18
11 12
1 4
5 7
17 19
1 15
14 20
5 9
17 18
2 5
13 19
16 19
11 14
12 17
16 20
5 15
2 4
3 10
5 13
10 16
3 14
5 10

output:

524288

result:

ok 1 number(s): "524288"

Test #34:

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

input:

26 49
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
1 26
2 26
3 26
4 26
5 26
6 26
7 26
8 26
9 26
10 26
11 26
12 26
13 26
14 26
15 26
16 26
17 26
18 26
19 26
20 26
21 26
22 26
23 26
24 26
25 26

output:

33554432

result:

ok 1 number(s): "33554432"

Test #35:

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

input:

26 49
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
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

output:

33554432

result:

ok 1 number(s): "33554432"

Subtask #4:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #36:

score: 0
Wrong Answer
time: 49ms
memory: 5036kb

input:

400 400
46 178
7 344
33 271
115 319
310 379
172 362
159 316
228 282
110 286
7 56
194 395
182 294
93 325
53 258
105 211
84 168
270 307
211 339
68 345
53 180
182 387
61 351
73 226
201 238
229 373
308 363
191 263
14 147
94 108
302 363
86 291
208 306
77 304
4 396
188 383
123 332
41 322
162 303
251 293
1...

output:

294967268

result:

wrong answer 1st numbers differ - expected: '8589717', found: '294967268'
English 繁體中文 简体中文

服务器时间: 2025-02-01 22:57:28 | 开源项目