QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#386059#495. 特征多项式Hanghang100 ✓440ms7692kbC++141.1kb2024-04-11 11:28:192024-04-11 11:28:19

Judging History

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

  • [2024-04-11 11:28:19]
  • 评测
  • 测评结果:100
  • 用时:440ms
  • 内存:7692kb
  • [2024-04-11 11:28:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=503,H=998244353;
ll n,a[N][N],p[N][N];
ll Ksm(ll x,ll y)
{
	ll s=1;
	for(ll i=1;i<=y;i<<=1,x=x*x%H)if(i&y)s=s*x%H;
	return s; 
}
void Guass()
{
	for(int i=2;i<=n;i++)
	{
		int z=i;
		while(z<=n&&!a[z][i-1])z++;
		if(z>n)continue;
		swap(a[i],a[z]);
		for(int j=1;j<=n;j++)swap(a[j][i],a[j][z]);
		ll ivi=Ksm(a[i][i-1],H-2);
		for(int j=i+1;j<=n;j++)
		{
			ll kk=a[j][i-1]*ivi%H;
			for(int k=i-1;k<=n;k++)a[j][k]=(a[j][k]-kk*a[i][k]%H+H)%H;
			for(int k=1;k<=n;k++)a[k][i]=(a[k][i]+kk*a[k][j])%H; 
		}
	}
}
void Heisenberg()
{
	p[0][0]=p[1][1]=1;p[1][0]=H-a[1][1];
	for(int i=2;i<=n;i++)
	{
		p[i][0]=p[i-1][0]*(H-a[i][i])%H;
		for(int j=1;j<=n;j++)p[i][j]=(p[i-1][j-1]-p[i-1][j]*a[i][i]%H+H)%H;
		for(int k=1;k<i;k++)
		{
			ll tr=a[i-k][i];
			for(int j=i-k+1;j<=i;j++)tr=tr*a[j][j-1]%H;
			for(int j=0;j<=n;j++)p[i][j]=(p[i][j]-tr*p[i-k-1][j]%H+H)%H;
		}
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
	Guass();Heisenberg();
	for(int i=0;i<=n;i++)cout<<p[n][i]<<" ";
}

詳細信息

Subtask #1:

score: 40
Accepted

Test #1:

score: 40
Accepted
time: 2ms
memory: 5840kb

input:

50
266912498 835091017 452080669 685381424 269707314 292908762 277505221 781233421 510658789 799543577 844885899 736245256 651479261 844896506 567470542 729489183 865380130 158739155 271515176 36971482 560309217 933384827 499620370 303835488 898526954 987576590 241842859 41182893 341293849 605213418...

output:

488909123 756431221 522719354 951978025 984483028 387050789 839003474 848748729 73660946 209052570 320403467 985792247 238302602 122770365 34409213 78745907 924948119 307541553 345405190 163129920 563259563 986001663 141458166 25551990 791139280 232175672 762375976 600087241 336338772 680942975 5250...

result:

ok 51 numbers

Test #2:

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

input:

50
470678273 931734857 173352721 526457871 564130426 144761603 238284413 798285715 206930148 332346314 687681678 294963721 181182406 515511656 46100813 945445974 374317629 130585665 527491154 725966485 755969257 723669830 561898084 164297853 55523585 860412955 408854476 101766712 344026927 11828467 ...

output:

500690888 340666550 325539135 43023381 672879488 47272540 488022836 904320968 15688345 984235997 218771376 98618184 270181314 239322021 703572598 998196755 255817623 86098975 521582630 969927730 935353746 853568728 68762639 658690937 422065288 195011414 725200242 5039906 4878905 86343580 14481170 50...

result:

ok 51 numbers

Test #3:

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

input:

50
48899500 381211219 299788836 56920958 959156824 971041737 484974287 19547733 550577636 214511072 834328431 95706739 682950672 783392533 378308638 597816707 961471261 980884788 698255585 237408759 560714095 922543343 297541607 555332705 37604692 656981352 788863224 481690617 660928132 512289418 62...

output:

464949876 623467268 421351479 650769510 31659601 839092326 598626072 789839298 120391457 171462333 919348741 994405045 89280144 892229221 604813803 27723542 849578524 550310425 133416785 867726870 484288692 400658735 690325077 9431610 744078731 596216901 742358900 792206736 677789158 886757460 20147...

result:

ok 51 numbers

Test #4:

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

input:

50
228643496 876451643 902697538 718555500 645102927 219159751 269137215 696774171 844036627 77467756 111582864 581683866 896693441 94202327 254628275 356467469 797903002 65065995 189619 442809707 552834636 282195776 656883839 273235722 195122210 398255537 728437144 735044348 395081173 250800589 374...

output:

916781330 986233103 461238391 198479753 322108877 636022751 269040986 129817285 890470941 807917696 112053660 91853931 760554133 218536850 518993003 57711251 54246622 997048718 743038693 50685790 392587603 571636675 359452255 517418233 789402740 870776373 345445069 646358220 606760267 75669976 63154...

result:

ok 51 numbers

Test #5:

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

input:

50
428295526 48135338 800823901 797425263 932339130 115860260 884812489 782530718 917203847 670564000 569976727 675534958 58722650 203986592 219391154 504838792 254680329 175527132 940525750 839348677 561271414 967336049 10567701 42401155 256368070 580372817 279886060 176649156 504286393 995707315 1...

output:

477723728 542216234 803447534 728611381 650563788 596881449 104443224 63454675 129288296 598138820 736763444 558850563 870326120 315005723 3955284 454520413 896712345 845934773 147395439 336880272 506627058 928589435 136997393 334665760 354519342 748543842 359053821 4473501 339888677 907330522 52185...

result:

ok 51 numbers

Test #6:

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

input:

50
636489115 359459213 583118736 903338461 611979007 957833365 700117415 324202510 692128453 932413996 463760119 513944214 718854161 408999643 841942918 824340336 461011409 258557290 818749510 296433138 109813786 703674046 14052729 360929523 58241337 560463483 819368182 895355952 709872007 87162078 ...

output:

286771026 204175632 194231472 974582362 296432346 701265562 647225274 653224243 160678570 870900276 584242705 32077994 325548632 304016526 405207587 130241284 988581196 346652663 242909883 734117373 244016890 294518994 353810616 540333232 813316176 291603694 108816703 853102842 227981927 963939957 5...

result:

ok 51 numbers

Test #7:

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

input:

50
166915899 428276840 794671844 786172368 745431694 5246594 918614188 934550029 639111719 635970442 377277928 372052436 360917696 152265153 351362703 59086161 678243913 4770183 69060772 141786615 419637344 277933955 526909244 753941028 566394310 943390776 939729296 374879075 157228988 97705728 2009...

output:

928403772 637682710 945807348 821552146 182226060 718856933 665413318 861266484 336486904 673594952 924203342 308258963 285705085 28686562 619532698 520479181 577453964 715959515 299958142 41217183 920060282 532996124 571347379 363284075 997690496 351082970 470696893 770838684 463516555 339384700 71...

result:

ok 51 numbers

Test #8:

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

input:

50
463195174 475592504 759373487 380462837 779551650 210669573 117641975 71659597 495830145 822428914 723087267 1871057 784000454 963435486 794513321 252923819 866833275 153201062 527230737 769880042 326075865 107069854 128416209 152237640 641896316 109894524 992939425 440302812 318373192 134230543 ...

output:

241461413 180973435 255053703 821043977 931001349 813697046 700641557 116393538 950063353 95220313 384233539 103447137 352294375 206410921 770559497 339941398 412288985 679439918 474706977 87071320 639913292 614450134 51295143 923750654 744684097 875092864 796776853 513439468 630929733 397129705 488...

result:

ok 51 numbers

Test #9:

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

input:

50
918955993 646216535 106583373 866644380 378586367 118306107 183043625 137971309 920886174 386970727 123814836 557820171 576148351 477180529 14640986 247635775 482222225 171494718 252286048 805691137 433457092 986002673 712256749 941147523 292108000 461998922 974128636 589746303 882281920 72972349...

output:

749447508 236185473 590738949 174555428 180255466 496836372 388568139 671945179 338406428 884253726 281128497 127913856 185564433 193642348 753411849 981418289 917358415 873611126 309218200 665696842 173973792 915269378 824870490 809392291 213292293 421774457 728579177 952463790 986488806 365153805 ...

result:

ok 51 numbers

Test #10:

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

input:

50
607795798 338986304 226189406 713119255 477288834 141177701 480693918 991697662 210146203 303365239 46496810 818242129 531967525 961233243 118297445 347578886 696383889 920719889 677857145 116582158 428082053 678623860 612549750 239499575 184725440 769493969 518012285 322433335 65141099 754875503...

output:

606152767 600268533 481283778 721645463 78432713 751176363 6079839 920156307 770490975 633134480 249969042 157977810 627361638 144641508 521058099 822000339 327141839 301072329 454692182 155192658 110713620 358623424 479852978 113332575 871901622 821921762 848224239 254060678 561973508 92156777 8032...

result:

ok 51 numbers

Subtask #2:

score: 60
Accepted

Test #11:

score: 60
Accepted
time: 427ms
memory: 7608kb

input:

500
912067299 560421914 613266377 676357217 299801919 277177164 278302771 810389156 943836886 639998245 855554810 784105751 403876660 750427762 374514286 219539473 45338811 881611774 125191025 37880987 91597910 672490636 695938784 118178926 898788752 890452808 971253057 929997223 751058722 706074011...

output:

411952917 254592175 451400251 818965557 532778250 666970804 536460047 505161051 929283167 786922570 754069073 954726640 717012792 917820372 704043825 562067608 458934427 135383885 242198313 168704567 182881615 861981026 754052754 217072547 153408675 12583700 117509848 587526402 41948160 889462937 66...

result:

ok 501 numbers

Test #12:

score: 0
Accepted
time: 419ms
memory: 7692kb

input:

500
478232118 971447002 961643951 651463379 359188536 123592731 408022824 614021181 504095452 886945598 43715874 948661485 582979498 410248873 364355203 535898357 326378188 839299898 994431713 267477572 890626307 653440585 289330406 570609851 799704525 420393254 408639469 658540466 396480934 7273737...

output:

966854361 731487249 220705991 138219457 326075658 688968385 958713503 29859820 167247243 23533378 236212576 307202768 618591557 698364482 798632183 678786746 551912339 680944022 707888956 866671662 552659731 201730797 604559547 600827431 826290747 664548090 844381930 347354853 411550910 908798212 37...

result:

ok 501 numbers

Test #13:

score: 0
Accepted
time: 430ms
memory: 7568kb

input:

500
971659226 775203212 321969257 208871707 63163731 823348736 325563208 129859806 825478490 440312404 756311601 880495335 871478241 918478470 980321034 16691770 899590425 395905332 156215008 11371408 57719701 331310868 568010175 942336032 829876530 854332494 628878389 627800641 538580739 345829419 ...

output:

895779501 992381632 680725234 206972378 41829586 918214417 701437049 930598530 833809829 699636561 993699793 156042398 209795616 2564951 791091464 903838421 931349730 275189435 333775071 689582130 268197335 989769820 885166717 428149332 421390101 158306211 633885018 661153993 40662267 723405767 9597...

result:

ok 501 numbers

Test #14:

score: 0
Accepted
time: 440ms
memory: 7544kb

input:

500
681290477 140378005 868387737 534823776 46566086 240508934 788711752 564096560 383593333 931702710 770619422 585653527 512712109 176021584 476545841 993154663 129262458 920752148 728524150 583796797 236858577 645241316 806751071 533824196 502857808 59377741 661779115 626233249 876831120 58381992...

output:

155409399 33295093 318956235 680792784 289242686 480297870 232745107 872137491 480998240 600427122 910908548 65371020 442096981 263081324 96520055 873416272 161517266 860657983 751666672 621655842 591217915 931598345 945137492 290049750 250263414 330683700 360402639 349941694 904446178 667482494 398...

result:

ok 501 numbers

Test #15:

score: 0
Accepted
time: 433ms
memory: 7552kb

input:

500
527228530 713302805 252225419 187565855 937562990 102479246 575217338 967730310 163361576 162454672 391894087 724413932 963062041 835816047 316852164 533803530 689825133 342845846 306778437 541530171 19471147 918190990 479800302 171653747 681985504 131181430 10159477 523757904 196029047 44397569...

output:

199390933 307013992 81427301 300055230 584455749 883634283 339039051 397062411 465635742 896133587 240060259 276047522 224523285 743954285 760477097 600023083 609753133 434082909 588809512 853339536 352000633 829017346 624968504 827854001 426151758 121505667 108369012 826662485 784555433 295214420 6...

result:

ok 501 numbers