QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#89563	#5827. 异或图	hy233	70	1151ms	55100kb	C++14	2.5kb	2023-03-20 16:19:10	2023-03-20 16:19:14

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-20 16:19:14]
评测

测评结果：70
用时：1151ms
内存：55100kb

查看

[2023-03-20 16:19:10]
提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=18;
const int M=(1<<15);
const ll mod=998244353;
inline ll rd()
{
	ll x=0; bool f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-') f=0;
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=x*10+(ch^48);
	return f?x:-x; 
}
inline void inc(ll &x,ll y)
{ if((x+=y)>=mod) x-=mod; }
int n,m;
ll c,a[N],ma[N];
bool ed[M];
int mi[M];
ll f[M];
map<int,ll> dp[M];

ll g[2][2][2];
ll solve(int S)
{
	ll ans=0;
	bool bb=1;
	for(int i=62;i>=0;i--)
	{
		int rm=0,now=0,pre=1;
		memset(g,0,sizeof(g));
		g[0][0][0]=1;
		for(int j=1;j<=n;j++)
		{
			if(!(S>>(j-1)&1))
				continue;
			swap(now,pre);
			memset(g[now],0,sizeof(g[now]));
			if(a[j]>>i&1)
			{
				rm^=1;
				for(int p=0;p<=1;p++)
					for(int q=0;q<=1;q++)
						g[now][p][!q]=(g[now][p][!q]+(1+(a[j]&((1ll<<i)-1)))%mod*g[pre][p][q])%mod;
				for(int p=0;p<=1;p++)
					inc(g[now][1][p],g[pre][0][p]);
				for(int p=0;p<=1;p++)
					g[now][1][p]=(g[now][1][p]+(1ll<<i)%mod*g[pre][1][p])%mod;
			}
			else
			{
				for(int p=0;p<=1;p++)
					for(int q=0;q<=1;q++)
						g[now][p][q]=(g[now][p][q]+(1+(a[j]&((1ll<<i)-1)))%mod*g[pre][p][q])%mod;
			}
		}
		inc(ans,g[now][1][c>>i&1]);
		if(rm!=(c>>i&1))
		{
			bb=0;
			break;
		}
	}
	ans+=bb;
	return ans;
}

int main()
{
//	freopen("graph.in","r",stdin);
//	freopen("graph.out","w",stdout);
	n=rd(),m=rd(),c=rd();
	for(int i=1;i<=n;i++)
		a[i]=rd(),ma[i]=(a[i]+1)%mod;
	for(int S=1;S<(1<<n);S++)
	{
		for(int i=1;i<=n;i++)
			if((S>>(i-1)&1)&&(!mi[S]||a[mi[S]]>a[i]))
				mi[S]=i;
	}
	for(int S=0;S<(1<<n);S++)
		ed[S]=1;
	for(int i=1;i<=m;i++)
	{
		int u=rd(),v=rd();
		for(int S=0;S<(1<<n);S++)
			if((S>>(u-1)&1)&&(S>>(v-1)&1))
				ed[S]=0;
	}
	f[0]=1;
	for(int S=1;S<(1<<n);S++)
	{
		f[S]=ed[S];
		int u=0;
		for(;;u++)
			if(S>>u&1)
				break;
		for(int T=(S-1)&S;T;T=(T-1)&S)
		{
			if(!(T>>u&1)) continue;
			if(ed[S^T])
				inc(f[S],mod-f[T]);
		}
	}
	dp[0][0]=1;
	for(int S=1;S<(1<<n);S++)
	{
		int u=0;
		for(;;u++)
			if(S>>u&1)
				break;
		for(int T=S;T;T=(T-1)&S)
		{
			if(!(T>>u&1)) continue;
			for(const auto &v:dp[S^T])
			{
				int w=v.first;
				if(__builtin_popcount(T)&1)
				{
					w|=(1<<(mi[T]-1));
					dp[S][w]=(dp[S][w]+v.second*f[T])%mod;
				}
				else
					dp[S][w]=(dp[S][w]+ma[mi[T]]*v.second%mod*f[T])%mod;
			}
		}
	}
	ll ans=0;
	for(auto v:dp[(1<<n)-1])
		ans=(ans+solve(v.first)*v.second)%mod;
		
	printf("%lld\n",ans);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20

Accepted

Test #1:

score: 20

Accepted

time: 3ms

memory: 4968kb

input:

output:

result:

ok 1 number(s): "44"

Test #2:

score: 0

Accepted

time: 3ms

memory: 4904kb

input:

output:

result:

ok 1 number(s): "798"

Test #3:

score: 0

Accepted

time: 3ms

memory: 5120kb

input:

output:

result:

ok 1 number(s): "33"

Test #4:

score: 0

Accepted

time: 3ms

memory: 4984kb

input:

4 0 4
9 8 5 2

output:

result:

ok 1 number(s): "148"

Test #5:

score: 0

Accepted

time: 3ms

memory: 5132kb

input:

5 6 14
12 15 13 13 12
3 1
2 4
2 5
2 1
5 3
4 5

output:

result:

ok 1 number(s): "21337"

Test #6:

score: 0

Accepted

time: 0ms

memory: 4956kb

input:

output:

result:

ok 1 number(s): "42"

Test #7:

score: 0

Accepted

time: 0ms

memory: 4940kb

input:

output:

result:

ok 1 number(s): "552"

Test #8:

score: 0

Accepted

time: 0ms

memory: 4984kb

input:

output:

result:

ok 1 number(s): "70"

Test #9:

score: 0

Accepted

time: 3ms

memory: 4912kb

input:

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

output:

result:

ok 1 number(s): "1231"

Test #10:

score: 0

Accepted

time: 1ms

memory: 4972kb

input:

5 7 9
6 7 13 15 12
1 3
5 3
5 2
4 5
4 3
4 1
3 2

output:

result:

ok 1 number(s): "6223"

Test #11:

score: 0

Accepted

time: 3ms

memory: 5008kb

input:

3 0 3
15 7 12

output:

result:

ok 1 number(s): "104"

Test #12:

score: 0

Accepted

time: 1ms

memory: 4904kb

input:

output:

result:

ok 1 number(s): "17"

Test #13:

score: 0

Accepted

time: 3ms

memory: 5180kb

input:

output:

result:

ok 1 number(s): "5224"

Test #14:

score: 0

Accepted

time: 3ms

memory: 5000kb

input:

5 0 12
9 8 14 11 2

output:

result:

ok 1 number(s): "3006"

Test #15:

score: 0

Accepted

time: 3ms

memory: 4988kb

input:

3 1 1
6 10 4
3 1

output:

result:

ok 1 number(s): "30"

Subtask #2:

score: 50

Accepted

Dependency #1:

100%

Accepted

Test #16:

score: 50

Accepted

time: 6ms

memory: 5568kb

input:

9 27 705410105529944560
929827299070190972 733413770730537329 473007347105710981 190062421504120247 918561152768663129 196040702922254016 981530663192980241 203295856357272834 337150461958783092
2 8
7 9
8 9
2 3
9 2
2 7
9 5
9 4
4 8
1 7
6 3
6 1
4 1
6 5
2 4
2 1
9 3
9 6
7 3
7 5
5 2
4 5
2 6
3 1
3 8
4 3
8 6

output:

result:

ok 1 number(s): "5392583"

Test #17:

score: 0

Accepted

time: 6ms

memory: 5724kb

input:

9 7 788762650337246371
605340092851479114 625896945107761227 361131331380167081 572133549445050458 929899192003968010 340514051531987427 690728985364969400 268762741220048006 818120252827139346
5 8
9 6
6 1
1 9
9 8
5 1
4 5

output:

35237078

result:

ok 1 number(s): "35237078"

Test #18:

score: 0

Accepted

time: 3ms

memory: 5028kb

input:

7 8 968166787047166534
945734997493219809 465616677643913237 530128109571749460 717120283671096308 118646732725835921 510958884109370001 797022604947155276
5 2
4 7
1 2
6 5
4 2
4 6
1 6
6 3

output:

133871438

result:

ok 1 number(s): "133871438"

Test #19:

score: 0

Accepted

time: 267ms

memory: 21540kb

input:

12 21 341964498832651322
422448536649714733 488538974423366199 893293448611252565 879334133559023407 13516625885288091 43377983230712374 263189254162337644 474056776923289355 540904774976211471 103364876621830299 515157013276720499 213857038587555252
12 9
8 3
1 9
1 7
3 1
8 11
11 10
6 10
6 1
10 2
7 9...

output:

296076062

result:

ok 1 number(s): "296076062"

Test #20:

score: 0

Accepted

time: 63ms

memory: 10516kb

input:

11 42 215284372701527433
670445786006000260 969876209382224733 248721347029697734 375741447316879814 840434941395805804 187091598433077755 126574401069916039 764298539206353847 750906714570719526 387387869969339518 713140316419888823
1 10
2 5
1 7
4 11
3 11
2 7
4 5
9 5
1 6
3 4
10 9
11 9
3 7
2 1
8 11
...

output:

861118590

result:

ok 1 number(s): "861118590"

Test #21:

score: 0

Accepted

time: 3ms

memory: 4944kb

input:

7 20 619868500075052677
653541655679358091 619279335581334164 74945438024390700 772996180610853550 636253173293891586 125935970032544337 454311587629767538
7 3
4 5
6 7
2 7
4 2
5 3
4 6
2 6
7 4
5 7
2 5
6 3
5 1
2 3
3 4
1 7
2 1
1 3
5 6
4 1

output:

396474896

result:

ok 1 number(s): "396474896"

Test #22:

score: 0

Accepted

time: 1151ms

memory: 54924kb

input:

13 1 655058659126783551
220930961455414900 363602338013759573 443737606888655227 137555247528320912 492558319379424931 930253239754276705 727679308735300884 787033056632957722 29595553176095069 586820353385061840 342786039873677428 141912073483259823 800159879032310691
4 9

output:

504321097

result:

ok 1 number(s): "504321097"

Test #23:

score: 0

Accepted

time: 4ms

memory: 5356kb

input:

8 20 301184670062888420
242892377877643484 3476501038317923 44616426924438256 159029640149965614 908446126450853551 608694214104046729 348038770876101788 993564634039215219
5 7
3 8
3 4
8 5
4 6
7 1
6 7
2 4
7 4
3 6
1 2
8 4
8 1
5 4
7 8
1 6
2 5
3 1
8 2
1 4

output:

result:

ok 1 number(s): "4724341"

Test #24:

score: 0

Accepted

time: 2ms

memory: 4980kb

input:

6 11 392024297517399665
88458611428053942 931089704347713876 2933742226147026 827268679955144802 950336975252592744 47151195847292633
3 5
6 4
5 4
2 3
6 5
5 1
1 4
5 2
2 4
1 3
3 4

output:

708968421

result:

ok 1 number(s): "708968421"

Test #25:

score: 0

Accepted

time: 60ms

memory: 10516kb

input:

11 37 271739451037214460
146061942241336421 138038807419718309 876032468776218591 790840232774594443 931090305572222272 446985261776711380 111295394912463090 788835018487784052 490717555570673932 654796069953431186 30534002965260366
10 6
6 7
4 7
2 5
6 4
2 10
3 4
10 7
2 11
4 9
9 7
6 11
1 11
1 9
9 10
...

output:

405837840

result:

ok 1 number(s): "405837840"

Test #26:

score: 0

Accepted

time: 1ms

memory: 5248kb

input:

7 20 603717808363574959
741883086260303904 498239876637304614 692656406513867207 11452440849146981 847091012107531819 751030904432703677 42306162304440584
7 4
3 5
3 1
7 3
2 1
2 4
7 2
5 6
5 7
4 5
1 6
3 2
1 5
6 3
2 5
3 4
4 6
6 2
7 1
4 1

output:

409098870

result:

ok 1 number(s): "409098870"

Test #27:

score: 0

Accepted

time: 2ms

memory: 5052kb

input:

7 14 276788100956613806
955375196371523555 993133468996644095 851781246244565785 406378187351709927 103400146137304775 3339166120945122 878092054213365193
6 5
3 4
6 3
2 7
1 4
6 1
7 6
3 7
4 2
4 6
1 7
1 5
4 7
3 2

output:

424423580

result:

ok 1 number(s): "424423580"

Test #28:

score: 0

Accepted

time: 55ms

memory: 10444kb

input:

11 42 703121070332973172
453838237041390989 7923458002585165 10157854185578313 428694248761966896 99567674522515040 887169792891871053 685704683091155403 1114809813572478 44938950664511738 433569272578015242 743893677718957742
10 2
5 4
7 3
5 9
10 7
6 1
9 7
5 7
8 6
2 5
2 11
1 10
3 5
4 3
4 1
5 11
11 7...

output:

266801727

result:

ok 1 number(s): "266801727"

Test #29:

score: 0

Accepted

time: 5ms

memory: 5792kb

input:

9 30 557579472218086545
389315525875489778 580024732015329877 122856826128791692 353894892064461662 593243941610294518 367724855679451396 93186374563462910 566339146552758642 503166485328553628
1 2
6 4
7 6
7 2
5 7
6 2
7 3
5 1
9 2
5 6
8 3
1 9
2 3
7 4
6 3
7 8
4 5
8 9
9 7
1 7
6 9
1 4
4 3
2 4
2 5
1 6
8 ...

output:

949276406

result:

ok 1 number(s): "949276406"

Test #30:

score: 0

Accepted

time: 4ms

memory: 5160kb

input:

8 3 145845032992032081
128648457003011001 90366745088645729 628278583922604945 949868219248781702 205548014539121837 573918524435421016 330291118265768760 961310581410805998
4 6
8 3
8 5

output:

522900734

result:

ok 1 number(s): "522900734"

Test #31:

score: 0

Accepted

time: 1035ms

memory: 54868kb

input:

13 75 122013601152601020
102573945790661441 119801481456740433 918257918904279930 290942994898157004 263309413587975225 176964463128718582 761601089984502811 634241033261747054 571682868717366221 514639207383578779 104093621484438574 329127701356038973 75081873200425743
12 10
8 5
6 8
9 10
3 11
11 7
...

output:

692554911

result:

ok 1 number(s): "692554911"

Test #32:

score: 0

Accepted

time: 1089ms

memory: 55048kb

input:

13 64 329467924442467878
646292845363466402 340430390655540423 886810138845116533 39936097409539153 913432466960561002 602450520208761333 373828261638409015 667657474356136433 785467436052153428 146484939478409777 905868211050101145 17011363096280257 145760138946384094
12 11
5 7
6 2
7 4
7 11
13 2
3 ...

output:

649034073

result:

ok 1 number(s): "649034073"

Test #33:

score: 0

Accepted

time: 1138ms

memory: 54884kb

input:

13 66 384520332466220624
456964675653769808 680045069530079454 274948142501386066 134398246845947863 670356535886270750 178282565665823320 512794756447850828 50252545496862865 541422634474563231 961120209571547713 371355651307501836 186254550272900976 966822162226229042
8 13
13 1
2 4
2 1
6 10
8 9
4 ...

output:

658091946

result:

ok 1 number(s): "658091946"

Test #34:

score: 0

Accepted

time: 1119ms

memory: 54864kb

input:

13 65 572440567840425592
511814115740732885 663983644274559529 290152050813440086 965100648598673086 30857576447532207 38983595600942050 44868781971516033 852778926994745179 689837263233427103 463859563825515127 374239587300029375 570685282674371777 524325090774617958
13 9
9 1
8 11
7 2
7 8
7 13
5 7
...

output:

143909590

result:

ok 1 number(s): "143909590"

Test #35:

score: 0

Accepted

time: 248ms

memory: 21640kb

input:

12 47 770433712593606285
440182952918236765 194832650378037376 697219961142716540 563570699573734184 269618082361587938 55268899053737043 485296751296674284 998533476123971567 111577714986287643 348822154801743257 627132722657408754 18059004572680409
8 6
12 1
1 8
7 9
11 1
9 10
9 6
2 5
6 5
5 1
10 3
6...

output:

775067582

result:

ok 1 number(s): "775067582"

Test #36:

score: 0

Accepted

time: 232ms

memory: 21564kb

input:

12 55 4026650049374118
857996118172858941 88567476008765118 124350619367959778 367372126789516747 162295446852695236 401458281846570045 560683838805908801 180182810302793022 266620617912155367 15471844114452206 627626552161917860 304587113952804811
10 7
5 4
7 4
5 10
7 2
9 10
9 1
12 3
9 12
4 3
3 7
6 ...

output:

215932540

result:

ok 1 number(s): "215932540"

Test #37:

score: 0

Accepted

time: 1133ms

memory: 55080kb

input:

13 72 103008731614274418
363442214120251460 50427867905538777 595260092919904639 373828918204231160 590436074764227318 232099477938107397 236426318819808960 244361286929299921 731166249407001339 112590684380573953 704728975731111649 956279851373121643 397374860922230268
9 3
1 7
5 8
11 9
8 11
5 7
12 ...

output:

187894198

result:

ok 1 number(s): "187894198"

Test #38:

score: 0

Accepted

time: 1118ms

memory: 54924kb

input:

13 67 301754072747398126
265229440645252605 147893078440826980 324796610061770660 551587001457543179 760667349634888702 663754795357245527 13662180881282347 505883171963085228 700459283676605999 680916615477968075 346754098755067485 36257491903674274 90955993330063055
11 10
12 3
10 9
1 5
5 3
7 3
11 ...

output:

610716167

result:

ok 1 number(s): "610716167"

Test #39:

score: 0

Accepted

time: 1071ms

memory: 55100kb

input:

13 69 75403304803046764
425586910005736592 969627160068708952 8405841780640838 200628822715657197 443919674658362813 814581495306742342 380276028841733301 16989707177466348 680330714625880719 558713286113730870 9955498253036428 725789604884677928 365353215214093400
3 4
3 6
12 5
3 10
4 1
3 5
3 2
11 9...

output:

260792359

result:

ok 1 number(s): "260792359"

Test #40:

score: 0

Accepted

time: 236ms

memory: 21644kb

input:

12 56 869512898929058396
754220212722812283 166889637803908373 104797582558497589 528115017624931431 615539035822791815 118783102898342804 693208985325316886 154703682974820603 72071186025455087 848518128787570353 935988349833056226 57807088687352158
5 2
3 5
4 8
11 1
7 3
2 3
8 2
12 1
8 1
7 6
1 9
12 ...

output:

243805672

result:

ok 1 number(s): "243805672"

Test #41:

score: 0

Accepted

time: 3ms

memory: 5156kb

input:

4 0 266137408554724708
132280826017951321 850283254994779845 125636870147394639 582930455427494327

output:

774985478

result:

ok 1 number(s): "774985478"

Test #42:

score: 0

Accepted

time: 0ms

memory: 4992kb

input:

5 0 227375183671684403
838078019228775407 525418186087747640 57761599398559037 631551466152686290 559180159956140299

output:

767267818

result:

ok 1 number(s): "767267818"

Test #43:

score: 0

Accepted

time: 12ms

memory: 6792kb

input:

10 0 12788671132569757
97604854595547116 837007520784391111 15665557093666358 394749031141258240 72625652061598325 201830158728703466 9652200671985894 541584810371802861 840666350721214277 28209319880081489

output:

611951263

result:

ok 1 number(s): "611951263"

Test #44:

score: 0

Accepted

time: 0ms

memory: 5004kb

input:

6 0 123695341588462971
746972473676804132 975557135115047878 105838726424604358 739722922748391586 815745791731060342 436086535778078347

output:

964600451

result:

ok 1 number(s): "964600451"

Test #45:

score: 0

Accepted

time: 17ms

memory: 6820kb

input:

10 0 514811793088171031
59031476825104549 506730165360872294 201622444164879971 79022523342161951 806946332677854690 982921196100386080 615442285110985500 66715232445866401 85195983895901861 934202056826291570

output:

997996310

result:

ok 1 number(s): "997996310"

Test #46:

score: 0

Accepted

time: 3ms

memory: 4996kb

input:

3 0 217195448970700851
522826994884125301 493574146457808013 878001063403190253

output:

813992307

result:

ok 1 number(s): "813992307"

Subtask #3:

score: 0

Time Limit Exceeded

Test #47:

score: 0

Time Limit Exceeded

input:

14 0 731833687287532167
157552918690640051 900457311668526045 111217720157614956 84140984111060473 814012186135880499 784848789620248379 958953377683017264 105083874298571687 104921429970878846 44983041675142735 871013110538758030 686733907990421995 98063590462078176 495161493555059993

output:

result:

Subtask #4:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted