QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18055#59. Determinant of A+BzAppleblue17#30 1646ms16408kbC++3.9kb2022-01-15 22:55:212024-03-04 04:42:02

Judging History

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

  • [2024-05-05 11:54:08]
  • hack成功,自动添加数据
  • (/hack/617)
  • [2024-05-05 11:38:15]
  • hack成功,自动添加数据
  • (/hack/616)
  • [2024-03-04 04:42:02]
  • 管理员手动重测本题所有提交记录
  • 测评结果:30
  • 用时:1646ms
  • 内存:16408kb
  • [2024-03-04 04:35:40]
  • hack成功,自动添加数据
  • (/hack/552)
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 16:47:46]
  • 评测
  • 测评结果:30
  • 用时:2023ms
  • 内存:17064kb
  • [2022-01-15 22:55:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long N=660,mod=998244353;
long long n;
long long a[N][N],b[N][N],p[N][N];
long long f[N][N],ex;

long long ksm(long long a,long long x){
	long long tot=1;
	while(x){
		if(x&1) tot=tot*a%mod;
		a=a*a%mod;
		x>>=1ll;
	}
	return tot;
}

long long det(long long a[N][N],long long n){
	long long tot=1;
	for(long long k=1;k<=n;k++){
		long long st=0;
		for(long long i=k;i<=n;i++){
			if(a[i][k]){
				st=i;
				break;
			}
		}
		if(!st) return 0;
		
		if(st!=k){
			for(long long j=1;j<=n;j++) swap(a[k][j],a[st][j]);
			tot=mod-tot;
		}
		for(long long i=k+1;i<=n;i++){
			int x=a[i][k]*ksm(a[k][k],mod-2);
			for(int j=1;j<=n;j++) a[i][j]=(a[i][j]+mod-x*a[k][j]%mod)%mod;
		}
		tot=tot*a[k][k]%mod;
	}
	return tot;
}

void gauss(long long a[N][N],long long n){
	for(long long k=1;k<n;k++){
		long long st=0;
		for(long long i=k+1;i<=n;i++){
			if(a[i][k]){
				st=i;
				break;
			}
		}
		if(!st) continue;
		
		
		if(st!=k+1){
			for(long long j=1;j<=n;j++) swap(a[k+1][j],a[st][j]);
			for(long long j=1;j<=n;j++) swap(a[j][k+1],a[j][st]);
		}
		for(long long i=k+2;i<=n;i++){
			long long x=a[i][k]*ksm(a[k+1][k],mod-2)%mod;
			for(long long j=1;j<=n;j++)
				a[i][j]=(a[i][j]+mod-a[k+1][j]*x%mod)%mod;
			for(long long j=1;j<=n;j++)
				a[j][k+1]=(a[j][k+1]+a[j][i]*x%mod)%mod;
		}
	}
	f[0][0]=1;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<i;j++){
			long long tot=a[j][i];
			for(long long k=j;k<i;k++) tot=tot*(mod-a[k+1][k])%mod;
			for(long long t=0;t<=i;t++) f[i][t]=(f[i][t]+f[j-1][t]*tot%mod)%mod;
		}
		for(long long t=0;t<=i;t++) f[i][t]=(f[i][t]+f[i-1][t]*a[i][i]%mod)%mod;
		for(long long t=1;t<=i;t++) f[i][t]=(f[i][t]+f[i-1][t-1])%mod;
	}
}

bool INV(long long a[N][N],long long b[N][N],long long n){
	for(long long k=1;k<=n;k++){
		long long st=0;
		
		while(1){
			for(long long i=k;i<=n;i++){
				if(b[i][k]){
					st=i;
					break;
				}
			}
			if(st) break;
			
			long long q=0;
			for(long long j=k;j<=n;j++){
				if(b[k][j]){
					q=j;
					break;
				}
			}
			if(q){
				for(long long i=1;i<=n;i++) swap(b[i][k],b[i][q]),swap(a[i][k],a[i][q]),swap(p[i][k],p[i][q]);
			}
			else{
				ex++;
				if(ex>n) return 0;
				for(long long j=1;j<=n;j++) b[k][j]=a[k][j],a[k][j]=0;
				for(long long i=1;i<k;i++){
					long long x=b[k][i]*ksm(b[i][i],mod-2)%mod;
					for(long long j=1;j<=n;j++)
						b[k][j]=(b[k][j]+mod-b[i][j]*x%mod),
						a[k][j]=(a[k][j]+mod-a[i][j]*x%mod),
						p[k][j]=(p[k][j]+mod-p[i][j]*x%mod);
				}
			}
		}
		
		if(st!=k){
			for(long long j=1;j<=n;j++) swap(b[k][j],b[st][j]),swap(a[k][j],a[st][j]),swap(p[k][j],p[st][j]);
		}
		for(long long i=1;i<=n;i++){
			if(i==k) continue;
			long long x=b[i][k]*ksm(b[k][k],mod-2)%mod;
			for(long long j=1;j<=n;j++)
				b[i][j]=(b[i][j]+mod-b[k][j]*x%mod)%mod,
				a[i][j]=(a[i][j]+mod-a[k][j]*x%mod)%mod,
				p[i][j]=(p[i][j]+mod-p[k][j]*x%mod)%mod;
		}
	}
	for(long long k=n;k>=1;k--){
		long long x=ksm(b[k][k],mod-2);
		for(long long j=1;j<=n;j++)
			b[k][j]=b[k][j]*x%mod,a[k][j]=a[k][j]*x%mod,p[k][j]=p[k][j]*x%mod;
		
		for(long long i=k+1;i<=n;i++){
			long long x=b[k][i];
			for(long long j=1;j<=n;j++){
				b[k][j]=(b[k][j]+mod-b[i][j]*x%mod)%mod,
				a[k][j]=(a[k][j]+mod-a[i][j]*x%mod)%mod,
				p[k][j]=(p[k][j]+mod-p[i][j]*x%mod)%mod;
			}
		}
	}
	return 1;
}


int main(){
//	freopen("1.txt","r",stdin);
	cin>>n;
	for(long long i=1;i<=n;i++)
		for(long long j=1;j<=n;j++)
			cin>>a[i][j];
	for(long long i=1;i<=n;i++)
		for(long long j=1;j<=n;j++)
			cin>>b[i][j];
	for(long long i=1;i<=n;i++) p[i][i]=1;
	if(!INV(a,b,n)){
		for(long long i=0;i<=n;i++) cout<<0<<" ";
		return 0;
	}
	gauss(a,n);
	
	long long x=ksm(det(p,n),mod-2);
	for(long long i=ex;i<=n;i++) cout<<f[n][i]*x%mod<<" ";
	for(long long i=1;i<=ex;i++) cout<<0<<" ";
//	cout<<x;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 12020kb

input:

50
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 179093706 0 0 0 0 0 873235003 0 873022990 0 0 0 0 150372208 0 0 0 0 0 0 0 0
540031202 441544333 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 30490606 0 23238599 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0 469112498 986185639 681339401 45702246 253041865 901928727 124272906 841147232 892298307 282587624 36844497 496481639 923774556 363290938 734076221 606138308 595123496 798750165 610620057 820264251 270948412 276081799 447257481 82518154 154567221 915942973 790594188 673758647 669644103 284181492 4...

result:

wrong answer 2nd numbers differ - expected: '436083536', found: '469112498'

Subtask #2:

score: 30
Accepted

Test #51:

score: 30
Accepted
time: 1630ms
memory: 16388kb

input:

500
0 0 0 0 0 482890969 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1077401 0 0 210804413 0 508044994 0 0 0 398405351 0 0 0 0 0 0 0 171917316 0 0 0 0 0 0 0 0 0 0 0 429230725 0 0 0 0 0 45665526 0 0 0 925078893 0 0 396149045 0 0 0 595858405 0 0 0 0 0 57208...

output:

197564738 776338137 450758758 86100992 615937344 559163914 131406243 401619987 648971457 913370895 305548921 393285962 915689006 605421884 878026660 574429045 573319599 364491109 147359659 277065849 558700076 605737085 416281513 704015976 726983797 205432732 98536178 813856939 885823882 179190007 66...

result:

ok 501 numbers

Test #52:

score: 0
Accepted
time: 1635ms
memory: 16408kb

input:

500
524607538 0 0 195818222 598065776 740433868 0 0 0 0 0 0 584106646 508647343 0 0 0 385186156 0 0 0 748826373 0 0 0 709897533 880532113 0 0 0 0 0 0 0 0 0 480030784 0 0 33138693 0 0 0 0 207633173 0 147270533 0 0 0 0 0 172244086 0 277695222 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 385815514 0 947687701 2...

output:

824902737 425089841 111211053 92073920 901320657 429074841 361764105 48023490 25552725 331325644 371920415 490762692 97825049 353418227 830075621 213540283 914362905 715071163 806070758 910602330 331161583 233467656 349280733 861811395 290106373 974369041 564660867 275072365 75983469 522667016 70935...

result:

ok 501 numbers

Test #53:

score: 0
Accepted
time: 1606ms
memory: 16388kb

input:

500
0 398190947 624334613 582987942 0 921082574 0 17867538 0 882918848 0 0 0 0 0 0 90859360 987403245 0 0 0 0 0 0 0 0 0 0 0 0 0 403400811 206487768 0 18198869 0 0 0 651523038 0 192277158 0 0 880215749 0 48622723 931175582 0 380135628 0 187644792 600194396 306519041 0 0 0 646257188 970944730 0 0 0 0 ...

output:

529709961 782389501 427087181 171575244 807733566 948768941 227470506 729203216 600000785 571222788 426790680 997717883 801879168 465532628 857973057 906830434 952735394 45567541 544721647 962896743 742244545 82712613 959513155 325015907 233661306 823083787 9502003 223215085 232986129 315518020 8220...

result:

ok 501 numbers

Test #54:

score: 0
Accepted
time: 1627ms
memory: 16344kb

input:

500
889477026 0 0 645288850 0 0 0 597784849 276670294 0 11781884 0 0 0 0 102328605 122546943 466795725 0 0 0 0 0 977951016 0 0 0 0 0 0 0 0 0 441400243 0 607727318 981252464 766407804 0 0 0 0 0 0 0 12674018 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 237392793 0 844896171 0 0 0 868060819 811717128 ...

output:

288878507 103918577 627843934 606769115 701195355 204316868 196692744 438647132 951275060 766989005 835482214 627619453 577296224 790244323 616919000 110197298 388088246 175117021 852199104 324078444 225511335 640854847 85621368 111580084 763931389 778949588 371252595 131117484 889375904 163824154 8...

result:

ok 501 numbers

Test #55:

score: 0
Accepted
time: 1614ms
memory: 16272kb

input:

500
0 0 472907806 0 0 0 0 0 0 0 0 298001434 0 896885439 0 0 0 0 0 0 0 0 0 0 0 8484835 0 0 0 0 0 0 0 0 0 0 0 0 954775009 0 0 0 0 288641397 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 512435253 0 0 0 0 0 0 0 386794324 0 655001487 0 0 468232155 0 0 0 0 0 0 0 0 75466257 0 0 0 0 0 0 74943...

output:

748044473 495654177 770128837 803264522 500024782 363477079 635161545 374689496 309423961 60457280 220603722 725110497 211554274 483787612 417355740 860542674 222191891 579668034 936747129 810487962 924847717 455094044 702324829 104318236 971133785 696909055 744480349 911219026 235872106 543656615 5...

result:

ok 501 numbers

Test #56:

score: 0
Accepted
time: 1646ms
memory: 16332kb

input:

500
0 0 316262547 241295061 242829688 550075323 245190856 935894298 504227016 176442273 184386996 0 575589507 830192730 0 557943520 895719881 60265103 747418748 261971973 0 99105521 0 69394805 134350353 205033556 151945738 123374702 411264285 912324098 94051646 306060455 899455875 830911129 63742779...

output:

381911851 916241926 514339398 858059197 875456460 714921300 302795193 409031920 783184712 867455007 766476017 243857202 697599556 921790119 792928980 251505819 994285379 59773659 613948150 272434631 907707976 207774347 94674353 668702663 837211956 421611818 372233312 483621202 904224325 602569053 47...

result:

ok 501 numbers

Test #57:

score: 0
Accepted
time: 1616ms
memory: 16264kb

input:

500
0 0 0 0 0 0 0 610990574 461613184 433655130 0 0 388974760 806398739 360535781 0 0 0 753732657 0 0 0 0 300470084 0 799888093 321915786 0 731888269 93322740 0 0 0 0 0 0 718357562 0 0 470844951 0 0 0 0 249536634 0 0 720846833 0 0 0 0 0 375498602 834962478 0 0 747200658 0 0 0 0 0 0 179664325 5290568...

output:

686260393 252245335 487730469 316503441 65416924 414972730 492614441 687219169 31213691 279281581 975310019 317336196 211707471 522955573 667053639 354126512 154392544 651273989 460079160 129443229 861736087 105977196 569334344 960887538 833748346 509178819 299462294 951455142 655102577 313951685 21...

result:

ok 501 numbers

Test #58:

score: 0
Accepted
time: 1621ms
memory: 16276kb

input:

500
105334543 923544035 0 0 916350532 0 893135971 0 38147030 0 787201908 432732664 0 721024223 708486999 0 701283493 0 0 0 763668271 0 109489133 715738358 0 218182028 0 486065021 0 0 0 853561005 114023429 0 0 601209488 0 101719806 611085551 10556195 0 0 200722083 810064594 0 428296558 88047945 0 905...

output:

386146069 360751156 993393533 927105682 228457601 648163753 787797973 522013271 115473192 964895477 558385286 95058804 298276053 139741955 517593941 927888946 390532694 926469984 546568354 927488188 867723462 62784459 519368506 183331379 408840670 685223323 395691605 356482931 538780329 800704761 25...

result:

ok 501 numbers

Test #59:

score: 0
Accepted
time: 1631ms
memory: 16264kb

input:

500
557789613 330510931 0 0 518024711 0 177752966 206203179 584083921 0 621770000 463398931 325609625 655715403 0 644837061 920744971 211652106 501844095 0 31815431 0 508411090 0 299431284 579451022 0 0 560290181 405509081 925573968 0 687385031 953919102 11971443 653210418 0 460457820 270650741 0 19...

output:

237337972 304001552 19756092 903398432 956462082 763470480 729301817 271753612 613700267 334841355 744710574 845246375 971151604 973253901 927943894 280393511 949928036 38722121 474176453 8825977 60878082 249547234 597102095 651053724 429068288 490083950 904742452 549860299 952659239 940608813 73417...

result:

ok 501 numbers

Test #60:

score: 0
Accepted
time: 1598ms
memory: 16372kb

input:

500
197401552 830689262 490108468 0 0 0 0 776237119 0 0 699253214 0 0 0 0 0 0 0 655156087 0 14751376 0 0 0 0 228028861 0 0 0 0 503139922 29233876 0 0 0 291395502 182147419 0 0 0 0 0 924694232 0 0 0 0 0 295585170 0 0 0 0 0 0 0 985603432 0 0 50944168 0 0 0 0 0 799660697 0 0 0 131935150 0 0 0 542518152...

output:

343481215 28530470 415182965 106440692 639253380 869174304 723450686 994252880 231059922 452274668 353261722 628878909 809794578 375900072 590410066 750447055 418962912 956023947 26017162 793161094 816016177 757605421 521424576 503928843 225335613 154352919 240264199 356448940 826417044 553721500 16...

result:

ok 501 numbers

Subtask #3:

score: 0
Skipped

Dependency #1:

0%