QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140120#5411. 杏仁Lynkcat#35 3014ms222072kbC++172.4kb2023-08-15 09:25:152024-07-04 01:42:56

Judging History

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

  • [2024-07-04 01:42:56]
  • 评测
  • 测评结果：35
  • 用时：3014ms
  • 内存：222072kb
查看
  • [2023-08-15 09:25:15]
  • 提交

answer

#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) (int)((x).size())
// #define int ll
#define N 22
using namespace std;
int dp[N][1<<N];
int pw[100005];
int f[N][N];
int F[1<<N];
int n,m,s,t;
int sm[1<<N];
int q;
inline ll quickPower(ll x,ll y)
{
	ll res=1;
	while (y)
	{
		if (y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
void BellaKira()
{
	pw[0]=1;
	for (int i=1;i<=100000;i++) pw[i]=1ll*pw[i-1]*2%mod;
	cin>>n>>m;
	cin>>s>>t;
	s--,t--;
	// for (int i=0;i<n;i++)
		// for (int j=i+1;j<n;j++)
			// f[i][j]=1,f[j][i]=1;
	for (int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		x--,y--;
		f[x][y]++;
	}
	for (int i=0;i<n;i++)
		if (i!=s&&i!=t)
			dp[i][(1<<i)]=f[i][t];
	for (int i=0;i<(1<<n);i++)
		for (int x=0;x<n;x++)
			if ((i>>x)&1)
				if (dp[x][i])
				{
					for (int y=0;y<n;y++)
						if (y!=s&&y!=t&&!((i>>y)&1))
						{
							int v=1ll*dp[x][i]*f[y][x]%mod;
							dp[y][i|(1<<y)]=(dp[y][i|(1<<y)]+v
							>=mod?dp[y][i|(1<<y)]+v-mod:dp[y][i|(1<<y)]+v);
						}
				}
	for (int i=0;i<(1<<n);i++)
		for (int x=0;x<n;x++)
		{
			int coef=1ll*dp[x][i]*f[s][x]%mod;
			dp[x][i]=coef;
			sm[i]=(sm[i]+coef>=mod?sm[i]+coef-mod:sm[i]+coef);
		}
	F[0]=1;
	for (int i=1;i<(1<<n);i++)
		if (!((i>>s)&1)&&!((i>>t)&1))
		{
			int t=__lg(i);
			ll nw=0;
			for (int j=i;j;j=(j-1)&i)
			{
				if (((j>>t)&1))
				{
					nw=(nw+1ll*F[i^j]*sm[j]%mod);
				} else break;
			}
			nw%=mod;
			F[i]=nw;
		}
	// return;
	for (int j=0;j<n;j++)
		for (int i=0;i<(1<<n);i++)
			if ((i>>j)&1)
				F[i]=(F[i]+F[i-(1<<j)])%mod;
	cin>>q;
	int ful=(1<<n)-1-(1<<s)-(1<<t);
	// cout<<F[ful]<<endl;
	while (q--)
	{
		int x;
		cin>>x;
		x--;
		// cout<<"??"<<x<<endl;
		if (x==s)
		{
			cout<<0<<'\n';
			continue;
		}
		if (x==t)
		{
			cout<<1ll*F[(1<<n)-1-(1<<s)-(1<<t)]
			*(pw[f[s][t]]-1)%mod<<'\n';
			continue;
		}
		int ans=0;
		for (int i=0;i<(1<<n);i++)
			if ((i>>x)&1)
				if (dp[x][i])
					ans=(ans+1ll*F[ful^i]*dp[x][i]%mod)%mod;
		cout<<1ll*ans*(pw[f[s][t]])%mod<<'\n';
	}
}
signed main()
{
	IOS;
	cin.tie(0);
	int T=1;
	while (T--)
	{
		BellaKira();
	}
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

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

input:

5 10
1 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
4
2
3
4
5

output:

20
14
10
15

result:

ok 4 lines

Test #2:

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

input:

2 0
1 2
0

output:

result:

ok 0 lines

Test #3:

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

input:

4 20
1 4
1 4
2 4
1 4
2 4
1 1
3 4
3 1
2 4
1 3
1 3
3 2
2 3
4 1
3 1
2 3
1 4
3 2
4 4
3 1
1 4
4
2
4
3
2

output:

0
225
224
0

result:

ok 4 lines

Test #4:

score: 0
Accepted
time: 2ms
memory: 13952kb

input:

5 20
1 5
1 5
1 2
4 2
5 3
1 1
1 4
4 5
5 1
1 3
2 5
2 4
3 1
5 2
4 3
4 3
3 4
5 1
4 2
4 5
3 4
5
3
4
2
5
5

output:

24
12
18
22
22

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 2ms
memory: 13824kb

input:

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

output:

52
0
60
0
68
0

result:

ok 6 lines

Test #6:

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

input:

11 20
3 1
3 1
3 7
9 1
4 9
7 4
9 11
6 11
9 5
3 5
3 7
8 9
1 7
10 1
6 11
11 5
3 7
8 10
7 1
9 7
11 8
10
2
10
7
8
11
1
6
9
5
1

output:

0
0
18
0
0
10
0
0
0
10

result:

ok 10 lines

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #7:

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

input:

11 9728
6 10
6 10
9 10
5 10
6 4
4 10
1 6
8 10
3 8
1 10
9 7
5 3
6 4
6 5
11 6
9 6
6 6
3 10
2 4
2 11
6 10
6 2
6 5
10 6
2 10
11 2
9 10
1 10
9 10
7 8
3 1
8 3
3 7
9 11
2 9
6 4
10 11
8 4
2 10
11 10
6 3
6 10
6 11
1 11
6 9
7 11
8 3
9 7
2 1
11 2
6 2
4 1
3 10
6 6
6 11
3 2
10 10
7 10
7 10
6 6
6 8
4 3
4 10
4 2
1...

output:

18074853
107213401
341119309
102827400
474349010
797006791
628391650
336670841
867783896
401391226
341119309

result:

ok 11 lines

Test #8:

score: 0
Accepted
time: 3ms
memory: 28244kb

input:

11 9613
4 1
4 1
8 9
11 1
7 8
4 10
2 1
6 11
4 2
11 9
5 7
11 6
2 6
11 2
3 9
3 9
1 1
6 3
1 6
3 1
2 1
10 5
4 9
4 2
10 1
7 8
6 8
3 1
9 11
4 9
5 1
1 7
11 3
10 8
8 11
2 9
3 1
7 1
8 1
7 8
4 4
4 7
3 7
1 1
6 1
4 6
5 1
8 7
4 4
1 6
4 9
4 11
5 3
10 7
7 2
6 5
4 9
4 9
8 7
5 1
4 1
1 1
4 6
11 1
3 7
8 11
6 1
1 10
8 4...

output:

182705163
786446186
459586140
963615780
865915814
315502014
910204714
865915814
514046009
72155443
281775231

result:

ok 11 lines

Test #9:

score: 0
Accepted
time: 6ms
memory: 24176kb

input:

11 9669
10 6
10 6
10 7
10 9
2 6
4 6
10 6
10 6
11 1
3 9
4 10
1 8
9 11
3 9
3 5
1 6
11 7
4 6
2 11
3 6
6 7
3 5
8 11
6 11
3 10
10 9
8 2
2 8
11 3
10 7
3 6
10 9
3 6
5 7
11 8
8 6
7 11
4 2
4 3
3 5
6 1
10 1
11 4
10 11
3 8
6 8
10 7
3 2
1 6
3 9
3 2
6 3
9 2
10 2
5 8
7 6
11 3
10 3
8 4
2 3
10 5
10 8
9 4
4 3
5 6
10...

output:

149327198
149327198
621010244
313847170
72070176
640755787
768354631
327768688
860362353
839515336
716753550

result:

ok 11 lines

Test #10:

score: 0
Accepted
time: 2ms
memory: 24160kb

input:

11 9989
8 4
8 4
8 10
6 3
5 4
3 10
8 5
1 6
2 4
7 4
3 2
5 8
11 4
11 4
8 5
9 1
5 8
11 3
8 4
8 4
4 3
3 4
8 1
2 3
11 9
3 6
2 11
8 6
4 10
5 4
3 5
5 4
10 3
5 11
9 6
8 4
1 10
2 7
11 3
8 11
2 3
2 11
7 4
2 6
8 1
8 4
8 11
2 9
9 1
8 9
5 4
8 8
3 4
9 11
8 5
8 2
6 2
9 4
10 1
8 4
10 2
5 8
8 4
8 4
10 6
8 4
2 1
10 4
...

output:

925008018
925008018
417424703
233031232
592456114
905513142
507449485
987584281
67045289
93256542
679477325

result:

ok 11 lines

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #11:

score: 15
Accepted
time: 80ms
memory: 37948kb

input:

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

output:

495528391
190001284
700736504
375686904
65816767
495528391
159308841
716930343
767343668
644562391
605875454
655781543
517152891
728480649
862738224
186485114
473518401

result:

ok 17 lines

Test #12:

score: 0
Accepted
time: 83ms
memory: 37900kb

input:

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

output:

279235714
30374151
24538748
679469233
229435792
155945081
450016612
514325705
338303999
985948696
888015758
183228636
644327192
941925587
178117228
380944360

result:

ok 16 lines

Test #13:

score: 0
Accepted
time: 80ms
memory: 37900kb

input:

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

output:

908804301
908804301
307393040
186849899
781252717
119888384
204862051
534656059
895145247
661847250
924518557
467036885
58336416
491807201
908827619
558794051
946875930

result:

ok 17 lines

Test #14:

score: 0
Accepted
time: 77ms
memory: 39172kb

input:

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

output:

594645673
313755086
496861206
822384794
781137812
81453666
4716276
155386775
58356574
571636304
756397369
43308328
933629703
283926473
785522930
781137812
210317775

result:

ok 17 lines

Subtask #4:

score: 0
Time Limit Exceeded

Test #15:

score: 10
Accepted
time: 188ms
memory: 41556kb

input:

18 324
9 8
1 1
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
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 8
4 9
4 10
4 11
...

output:

256104819
256104819
238677015
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819
256104819

result:

ok 18 lines

Test #16:

score: 0
Accepted
time: 1206ms
memory: 120780kb

input:

20 400
13 20
1 1
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
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
3 19
3 20
4 1
4 2
4 3
4 ...

output:

681008066
681008066
681008066
681008066
681008066
681008066
681008066
681008066
205106617
681008066
681008066
681008066
681008066
681008066
681008066
681008066
681008066
681008066
681008066
681008066

result:

ok 20 lines

Test #17:

score: 0
Accepted
time: 3014ms
memory: 222072kb

input:

21 441
16 17
1 1
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
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
2 21
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
3 19
3 20
3 21...

output:

689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
689426186
319626977
689426186
689426186
689426186
689426186
689426186
689426186
689426186

result:

ok 21 lines

Test #18:

score: -10
Time Limit Exceeded

input:

22 484
10 1
1 1
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
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
2 17
2 18
2 19
2 20
2 21
2 22
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
3 17
3 18
3 19
...

output:

result:

Subtask #5:

score: 0
Runtime Error

Dependency #3:

100%
Accepted

Test #19:

score: 0
Runtime Error

input:

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

output:

result:

Subtask #6:

score: 0
Runtime Error

Test #23:

score: 0
Runtime Error

input:

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

output:

result:

Subtask #7:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%
English 繁體中文 简体中文

Server Time: 2024-12-02 16:01:39 | OpenSource Project