QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94426#7. 主旋律ushg8877100 ✓369ms3956kbC++17899b2023-04-05 22:06:352023-04-05 22:06:38

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-05 22:06:38]
  • 评测
  • 测评结果：100
  • 用时：369ms
  • 内存：3956kb
查看
  • [2023-04-05 22:06:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD=1e9+7;
int n,m;
int a[20];
ll pw[205],f[1<<16],g[1<<16];
// f 表示是强联通,g 表示强联通独立乘上容斥系数
int popcount(int x){int cnt=0;while(x)cnt++,x-=(x&-x);return cnt;}
int edge(int u,int v){
	int cnt=0;
	for(int i=0;i<n;i++)if(u>>i&1)cnt+=popcount(a[i]&v);
	return cnt;
}
void del(ll &x,ll y){x-=y;if(x<0)x+=MOD;}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;cin>>u>>v;
		a[u-1]|=(1<<v-1);
	}
	pw[0]=1;
	for(int i=1;i<205;i++) pw[i]=pw[i-1]*2%MOD;
	for(int i=1;i<(1<<n);i++){
		int t=(i&-i),k=i^t;// 固定一个点
		for(int j=(k-1)&k;j;j=(j-1)&k) del(g[i],g[k^j]*f[j|t]%MOD);
		if(t!=i) del(g[i],g[k]);
		f[i]=pw[edge(i,i)];
		for(int j=i;j;j=(j-1)&i) del(f[i],g[j]*pw[edge(i,i^j)]%MOD);
		g[i]+=f[i];g[i]%=MOD;
	}
	cout<<f[(1<<n)-1];
	return 0;
}
源文件, 语言: C++17

详细

Test #1:

score: 10
Accepted
time: 2ms
memory: 3436kb

input:

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

output:

9390

result:

ok single line: '9390'

Test #2:

score: 10
Accepted
time: 2ms
memory: 3328kb

input:

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

output:

100460

result:

ok single line: '100460'

Test #3:

score: 10
Accepted
time: 2ms
memory: 3432kb

input:

8 35
5 1
8 7
7 8
7 6
6 1
2 5
6 5
8 2
7 2
7 5
3 1
6 3
2 3
5 2
8 5
8 3
6 8
2 1
1 6
2 6
7 3
2 4
3 5
3 2
3 7
7 1
8 4
3 4
3 6
6 4
2 7
4 6
6 7
7 4
8 1

output:

299463717

result:

ok single line: '299463717'

Test #4:

score: 10
Accepted
time: 2ms
memory: 3264kb

input:

8 40
5 1
8 7
7 8
7 6
6 1
2 5
6 5
8 2
7 2
7 5
3 1
6 3
2 3
5 2
8 5
8 3
6 8
2 1
1 6
2 6
7 3
2 4
3 5
3 2
3 7
7 1
8 4
3 4
3 6
6 4
2 7
4 6
6 7
7 4
8 1
1 2
4 8
5 8
4 3
5 7

output:

21156439

result:

ok single line: '21156439'

Test #5:

score: 10
Accepted
time: 2ms
memory: 3436kb

input:

8 45
5 1
8 7
7 8
7 6
6 1
2 5
6 5
8 2
7 2
7 5
3 1
6 3
2 3
5 2
8 5
8 3
6 8
2 1
1 6
2 6
7 3
2 4
3 5
3 2
3 7
7 1
8 4
3 4
3 6
6 4
2 7
4 6
6 7
7 4
8 1
1 2
4 8
5 8
4 3
5 7
2 8
1 5
3 8
1 3
4 1

output:

426670664

result:

ok single line: '426670664'

Test #6:

score: 10
Accepted
time: 3ms
memory: 3508kb

input:

10 65
5 10
1 8
7 8
6 2
5 7
9 2
4 7
3 7
1 6
3 10
7 9
8 4
7 1
5 2
1 7
4 2
8 3
8 1
3 9
8 2
2 10
4 3
9 10
5 3
3 8
3 4
6 10
4 8
4 5
5 8
9 5
9 6
10 2
10 5
6 1
2 1
9 4
7 10
5 6
10 7
10 8
5 9
9 7
9 8
4 10
8 9
7 2
2 7
10 1
7 3
6 8
7 6
9 1
6 5
2 4
6 3
2 9
8 10
10 9
8 5
4 1
6 9
2 3
1 3
1 9

output:

931896041

result:

ok single line: '931896041'

Test #7:

score: 10
Accepted
time: 3ms
memory: 3272kb

input:

10 70
5 10
1 8
7 8
6 2
5 7
9 2
4 7
3 7
1 6
3 10
7 9
8 4
7 1
5 2
1 7
4 2
8 3
8 1
3 9
8 2
2 10
4 3
9 10
5 3
3 8
3 4
6 10
4 8
4 5
5 8
9 5
9 6
10 2
10 5
6 1
2 1
9 4
7 10
5 6
10 7
10 8
5 9
9 7
9 8
4 10
8 9
7 2
2 7
10 1
7 3
6 8
7 6
9 1
6 5
2 4
6 3
2 9
8 10
10 9
8 5
4 1
6 9
2 3
1 3
1 9
5 4
1 5
5 1
10 4
10 6

output:

303656759

result:

ok single line: '303656759'

Test #8:

score: 10
Accepted
time: 360ms
memory: 3956kb

input:

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

output:

717458968

result:

ok single line: '717458968'

Test #9:

score: 10
Accepted
time: 362ms
memory: 3780kb

input:

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

output:

459157220

result:

ok single line: '459157220'

Test #10:

score: 10
Accepted
time: 369ms
memory: 3800kb

input:

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

output:

663282473

result:

ok single line: '663282473'
English 繁體中文 简体中文

服务器时间: 2025-01-20 07:08:32 | 开源项目