QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#496566#7. 主旋律ucup-team365920 876ms4448kbC++14883b2024-07-28 13:18:192024-07-28 13:18:19

Judging History

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

  • [2024-07-28 13:18:19]
  • 评测
  • 测评结果：20
  • 用时：876ms
  • 内存：4448kb
查看
  • [2024-07-28 13:18:19]
  • 提交

answer

// Hydro submission #66a5d3aa79d4fe919e4d4787@1722143898732
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=15,mod=998244353;
int n,m,c,e[N],h[1<<N];
ll pw[N*N],f[1<<N],g[1<<N];
int E(int x,int y){int res=0;for(int i=0;i<n;i++)if(x>>i&1)res+=__builtin_popcount(e[i]&y);return res;}
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m,pw[0]=1;
    for(int i=1,x,y;i<=m;i++)cin>>x>>y,e[x-1]|=1<<y-1,pw[i]=pw[i-1]*2%mod;
    for(int i=0;i<1<<n;i++)for(int j=0;j<n;j++)if(i>>j&1)h[i]+=__builtin_popcount(e[j]&i);
    for(int i=1;i<1<<n;i++) {
        for(int j=(i-1)&i;j;j=(j-1)&i)if((i&-i)==(j&-j))g[i]=(g[i]-f[j]*g[i^j])%mod;
        f[i]=pw[h[i]];
        for(int j=i;j;j=(j-1)&i)f[i]=(f[i]+g[j]*pw[h[i^j]+E(j,i^j)])%mod;
        g[i]=(g[i]-f[i])%mod;
    }cout<<(f[(1<<n)-1]+mod)%mod<<'\n';
    return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

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

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

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: 0
Wrong Answer
time: 1ms
memory: 3752kb

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:

304730679

result:

wrong answer 1st lines differ - expected: '299463717', found: '304730679'

Test #4:

score: 0
Wrong Answer
time: 1ms
memory: 3560kb

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:

879671245

result:

wrong answer 1st lines differ - expected: '21156439', found: '879671245'

Test #5:

score: 0
Wrong Answer
time: 1ms
memory: 3604kb

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:

659237448

result:

wrong answer 1st lines differ - expected: '426670664', found: '659237448'

Test #6:

score: 0
Wrong Answer
time: 3ms
memory: 3556kb

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:

639324001

result:

wrong answer 1st lines differ - expected: '931896041', found: '639324001'

Test #7:

score: 0
Wrong Answer
time: 0ms
memory: 3812kb

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:

117618886

result:

wrong answer 1st lines differ - expected: '303656759', found: '117618886'

Test #8:

score: 0
Wrong Answer
time: 876ms
memory: 4156kb

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:

977330743

result:

wrong answer 1st lines differ - expected: '717458968', found: '977330743'

Test #9:

score: 0
Wrong Answer
time: 875ms
memory: 4448kb

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:

612584929

result:

wrong answer 1st lines differ - expected: '459157220', found: '612584929'

Test #10:

score: 0
Wrong Answer
time: 874ms
memory: 4228kb

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:

622877743

result:

wrong answer 1st lines differ - expected: '663282473', found: '622877743'
English 繁體中文 简体中文

Server Time: 2025-01-20 12:10:30 | OpenSource Project