QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#830966#7. 主旋律piggy123100 ✓234ms12876kbC++173.5kb2024-12-25 08:10:582024-12-25 08:10:59

Judging History

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

  • [2024-12-25 08:10:59]
  • 评测
  • 测评结果：100
  • 用时：234ms
  • 内存：12876kb
查看
  • [2024-12-25 08:10:58]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll pw[55*55],ga[55][55],dp[1ll<<15],g[1ll<<15],h[1ll<<15],cnt[1ll<<15],to1[15][1ll<<15],to2[15][1ll<<15],tot[1ll<<15],lg2[1ll<<15];
const ll mod=1e9+7;

int main(){
	ll n,m;
	cin >> n >> m;
	for (ll i=1;i<=m;i++){
		ll u,v;
		cin >> u >> v;
		u--,v--;
		ga[u][v]=1;
	} 
	pw[0]=1;
	for (ll i=1;i<=m;i++)pw[i]=pw[i-1]*2%mod;
	for (ll i=0;i<=(1ll<<n)-1;i++){
		if (i>1)
		lg2[i]=lg2[i>>1]+1;
		for (ll j=0;j<n;j++){
			for (ll k=0;k<n;k++){
				if (i>>k&1){
					to1[j][i]+=ga[j][k];
					to2[j][i]+=ga[k][j];
					if (i>>j&1){
						tot[i]+=ga[j][k];
					}
				}
			}
		}
	}
	g[0]=h[0]=dp[0]=1;
	for (ll i=0;i<=(1ll<<n)-1;i++){
		cnt[i]=0;
		for (ll j=i;j;j=(j-1)&i){
			if (j!=i){
				ll z=(i^j)&(-(i^j)),id=lg2[z];
				cnt[j]=cnt[j|z]+to2[id][j]-to1[id][i^j^z];
			}
		}
		for (ll j=i;j;j=(j-1)&i){
			if ((j&(i&-i))==(i&-i)){
				h[i]+=(mod-1)*h[i^j]%mod*g[j]%mod;
				h[i]%=mod;
			}
		}
		for (ll j=i;j;j=(j-1)&i){
			dp[i]+=(dp[i^j]+g[i^j])%mod*h[j]%mod*pw[cnt[j]]%mod;
			dp[i]%=mod;
		}
		g[i]=(pw[tot[i]]-dp[i]+mod)%mod;
		h[i]+=g[i],h[i]%=mod;
//		cout<<i<<":"<<dp[i]<<","<<g[i]<<","<<h[i]<< endl;
	}
	cout<<g[(1ll<<n)-1];
	return 0;
}

/*
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　■■■■■　　　　　■■　　　　　　■■■　　　　　■■■　　　■　　　　■　　　　　■　　　　　■■■■　　　　■■■■　　
　■　　　■■　　　　■■　　　　　■　　■■　　　■　　■■　　■　　　　■　　　　■■　　　　　■　　■■　　■■　　■　　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　■■■　　　　■■　　■■　　■　　　■■　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　　■■　　　　■　　　■■　　　　　　■■　
　■　　　　■　　　　■■　　　　■　　　　　　　■　　　　　　　　　■■　　　　　　■■　　　　　　　　■■　　　　　　■　　
　■　　　■■　　　　■■　　　　■　　■■■　　■　　■■■　　　　■■　　　　　　■■　　　　　　　■■　　　　　■■■　　
　■■■■■　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　　■■　　　　　　　　■■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■■　　　　　　　　　　■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■　　　　　　■　　　■■　
　■　　　　　　　　　■■　　　　■■　　■■　　■■　　■■　　　　■■　　　　　　■■　　　　■　　　　　　　■■　　■■　
　■　　　　　　　　　■■　　　　　　■■■■　　　　■■■■　　　　■■　　　　　　■■　　　　■■■■■■　　　■■■■　　
*/
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 0ms
memory: 11716kb

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

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: 0ms
memory: 11896kb

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: 0ms
memory: 9880kb

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: 0ms
memory: 11720kb

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

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

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: 225ms
memory: 12856kb

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: 222ms
memory: 12844kb

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: 234ms
memory: 12876kb

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 繁體中文 简体中文

Server Time: 2025-01-20 06:00:32 | OpenSource Project