QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#18056 | #59. Determinant of A+Bz | Appleblue17# | 30 | 1630ms | 16468kb | C++ | 3.9kb | 2022-01-15 22:56:23 | 2024-03-04 04:42:07 |
Judging History
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++){
long long x=a[i][k]*ksm(a[k][k],mod-2)%mod;
for(long long 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: 30
Accepted
time: 4ms
memory: 9972kb
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 436083536 175535903 554959884 223039496 58344364 587204040 55300817 397840744 155512976 415872342 477738866 352386530 53242600 485943331 139434001 914586784 544887336 464494428 399973492 144143987 524998117 938746522 91863621 401839366 833514493 170911469 632598634 939655150 515206919 825564296 65...
result:
ok 51 numbers
Test #2:
score: -30
Wrong Answer
time: 0ms
memory: 10048kb
input:
50 0 0 0 0 0 0 865147437 0 0 0 0 0 0 0 0 0 0 0 0 0 892479829 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 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19576557 0 203729377 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 874545437 0 0 0 0 0 0 0 0 ...
output:
0 0 0 -96508257 -444564496 -598632 -671734575 -911379972 -371355578 -402516428 -108175890 -221946633 -581330222 -474112816 -192686184 -770624125 -875727475 107722209 384032033 34511705 794989094 497436399 498172117 87775300 736550031 830235216 943160826 353411765 200450105 828651361 146478882 198315...
result:
wrong answer 4th numbers differ - expected: '0', found: '-96508257'
Subtask #2:
score: 30
Accepted
Test #51:
score: 30
Accepted
time: 1613ms
memory: 16432kb
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: 1603ms
memory: 16468kb
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: 1612ms
memory: 16316kb
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: 1622ms
memory: 16372kb
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: 1610ms
memory: 16440kb
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: 1623ms
memory: 16356kb
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: 1609ms
memory: 16340kb
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: 1605ms
memory: 16424kb
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: 1630ms
memory: 16312kb
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: 1599ms
memory: 16404kb
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%