QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #531306 | #7927. Fortune Telling | WaterSun | AC ✓ | 1058ms | 220240kb | C++14 | 1.6kb | 2024-08-24 19:49:34 | 2024-08-24 19:49:35 |
Judging History
answer
#include <bits/stdc++.h>
using llsi = long long signed int;
constexpr llsi mod = 998244353;
constexpr llsi ksm(llsi a, llsi b) {
llsi res = 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
constexpr inline llsi inv(llsi a) { return ksm(a, mod - 2); }
constexpr llsi inv6 = inv(6);
constexpr int $t = 10000;
int dp_base[$t * ($t + 1) >> 1];
inline int& dp(int i, int j) {
return dp_base[(i * (i - 1) >> 1) + j - 1];
}
void add(int &a, int b) { if((a += b) >= mod) a -= mod; }
std::vector<std::vector<int>> mem;
int get_dp(int i, int J) {
if(i <= $t) return dp(i, J);
if(J > i / 2) J = i - J + 1;
if(!mem[i].size()) {
mem[i].assign((i + 3) / 2, 0);
for(int j = 1, r = i; j <= r; j++, r--)
for(int k = 1; k <= 6; ++k) if((j - k + 6) % 6)
add(mem[i][j], inv6 * get_dp(i - (i - k + 6) / 6, j - (j - k + 6) / 6) % mod);
}
return mem[i][J];
}
int main() {
// std::cerr << "sizeof(dp_base) = " << sizeof(dp_base) / 1024.L / 1024.L << char(10);
int n; std::cin >> n;
mem.resize(n + 1);
for(int i = 1; i <= 6; ++i) for(int j = 1; j <= i; ++j) dp(i, j) = inv(i);
for(int i = 7; i <= $t; ++i) for(int j = 1; j <= i; ++j) {
for(int k = 1; k <= 6; ++k) if((j - k + 6) % 6)
add(dp(i, j), inv6 * dp(i - (i - k + 6) / 6, j - (j - k + 6) / 6) % mod);
}
std::vector<int> ans(n + 1);
for(int l = 1, r = n; l <= r; ++l, --r) ans[l] = ans[r] = get_dp(n, l);
int tot = 0;
for(int i = 1; i <= n; ++i) std::cout << ans[i] << char(10), add(tot, ans[i]);
// std::cerr << "tot = " << tot << char(10);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 939ms
memory: 198948kb
input:
3
output:
332748118 332748118 332748118
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 949ms
memory: 198960kb
input:
7
output:
305019108 876236710 876236710 876236710 876236710 876236710 305019108
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 940ms
memory: 199188kb
input:
8
output:
64701023 112764640 160828257 160828257 160828257 160828257 112764640 64701023
result:
ok 8 lines
Test #4:
score: 0
Accepted
time: 969ms
memory: 198948kb
input:
10
output:
409773145 853745402 299473306 743445563 189173467 189173467 743445563 299473306 853745402 409773145
result:
ok 10 lines
Test #5:
score: 0
Accepted
time: 936ms
memory: 199184kb
input:
11
output:
989514850 873566509 757618168 641669827 525721486 409773145 525721486 641669827 757618168 873566509 989514850
result:
ok 11 lines
Test #6:
score: 0
Accepted
time: 954ms
memory: 198896kb
input:
12
output:
175103562 138336949 101570336 64803723 28037110 989514850 989514850 28037110 64803723 101570336 138336949 175103562
result:
ok 12 lines
Test #7:
score: 0
Accepted
time: 951ms
memory: 198948kb
input:
13
output:
159099473 484299138 167572226 849089667 532362755 215635843 175103562 215635843 532362755 849089667 167572226 484299138 159099473
result:
ok 13 lines
Test #8:
score: 0
Accepted
time: 977ms
memory: 206832kb
input:
131091
output:
567383016 662994174 732938392 473447067 205102363 749004511 410127252 89326957 304368813 405336094 96918015 896888521 737639871 508973310 349553790 121346210 739328699 633788498 95902577 411856713 705314547 568274283 647209576 401593169 250679135 133612309 639836192 600464933 338261759 832985164 518...
result:
ok 131091 lines
Test #9:
score: 0
Accepted
time: 926ms
memory: 198956kb
input:
14
output:
947151085 589891892 674722122 956565255 240164035 522007168 561598032 561598032 522007168 240164035 956565255 674722122 589891892 947151085
result:
ok 14 lines
Test #10:
score: 0
Accepted
time: 932ms
memory: 199120kb
input:
15
output:
637039767 460763713 462646547 333815057 96269873 856969042 271282146 750138182 271282146 856969042 96269873 333815057 462646547 460763713 637039767
result:
ok 15 lines
Test #11:
score: 0
Accepted
time: 986ms
memory: 198948kb
input:
16
output:
228892706 883702432 747017242 402641198 772461176 894058019 115446252 447880564 447880564 115446252 894058019 772461176 402641198 747017242 883702432 228892706
result:
ok 16 lines
Test #12:
score: 0
Accepted
time: 930ms
memory: 199116kb
input:
17
output:
903981410 862346530 997767939 885172564 487381090 33762637 823581070 80265784 832169836 80265784 823581070 33762637 487381090 885172564 997767939 862346530 903981410
result:
ok 17 lines
Test #13:
score: 0
Accepted
time: 951ms
memory: 198924kb
input:
18
output:
31744296 579723162 218537119 508969018 404962409 246598953 48644633 989179173 465496473 465496473 989179173 48644633 246598953 404962409 508969018 218537119 579723162 31744296
result:
ok 18 lines
Test #14:
score: 0
Accepted
time: 951ms
memory: 198964kb
input:
19
output:
856240157 861682308 431212253 293953179 552074030 697393155 911422408 885288577 288395015 423610073 288395015 885288577 911422408 697393155 552074030 293953179 431212253 861682308 856240157
result:
ok 19 lines
Test #15:
score: 0
Accepted
time: 929ms
memory: 198888kb
input:
2
output:
499122177 499122177
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 946ms
memory: 198952kb
input:
20
output:
308054940 613046471 627077388 876731984 177753318 168429486 670640271 198941540 78614976 772809215 772809215 78614976 198941540 670640271 168429486 177753318 876731984 627077388 613046471 308054940
result:
ok 20 lines
Test #17:
score: 0
Accepted
time: 923ms
memory: 198896kb
input:
21
output:
982695520 584249571 230343344 502166250 95786010 45929897 966423983 499961052 602742551 195298383 571250409 195298383 602742551 499961052 966423983 45929897 95786010 502166250 230343344 584249571 982695520
result:
ok 21 lines
Test #18:
score: 0
Accepted
time: 958ms
memory: 198956kb
input:
22
output:
966781769 485759206 207027266 706375129 431325017 29239160 854886038 860244349 975296442 757095317 214558602 214558602 757095317 975296442 860244349 854886038 29239160 431325017 706375129 207027266 485759206 966781769
result:
ok 22 lines
Test #19:
score: 0
Accepted
time: 1045ms
memory: 213464kb
input:
220223
output:
904620830 570662262 259789297 26081430 875852152 157789135 813374609 696357431 573660829 912186928 302936478 446257515 508716017 720193773 61498818 573701804 35401989 335790053 147155562 720189556 202742334 898770323 563779215 679480614 964058891 284782141 780438196 409505450 327113979 435543803 703...
result:
ok 220223 lines
Test #20:
score: 0
Accepted
time: 943ms
memory: 198956kb
input:
23
output:
954917379 342974141 202729634 743468438 225594339 127313574 493000351 683716775 632060585 836560738 487438938 519382453 487438938 836560738 632060585 683716775 493000351 127313574 225594339 743468438 202729634 342974141 954917379
result:
ok 23 lines
Test #21:
score: 0
Accepted
time: 933ms
memory: 199184kb
input:
24
output:
256712450 792788255 185139400 273034571 946861660 148127765 140357905 475165095 323017527 125675762 14837461 810381738 810381738 14837461 125675762 323017527 475165095 140357905 148127765 946861660 273034571 185139400 792788255 256712450
result:
ok 24 lines
Test #22:
score: 0
Accepted
time: 916ms
memory: 199188kb
input:
25
output:
153416698 440842204 647469130 15934645 745917575 93482893 204648973 6858001 855572686 400724791 347023502 92626399 975164184 92626399 347023502 400724791 855572686 6858001 204648973 93482893 745917575 15934645 647469130 440842204 153416698
result:
ok 25 lines
Test #23:
score: 0
Accepted
time: 1056ms
memory: 215952kb
input:
258548
output:
998229469 629439999 402134423 170383211 700923501 737477855 550578018 344923565 321676219 551361431 772235781 242263252 669495215 760331984 72997460 201352514 202002143 103678134 215062996 686598324 303263772 128819864 878737293 118374274 606964849 351929974 928549936 104033200 728385527 249172889 2...
result:
ok 258548 lines
Test #24:
score: 0
Accepted
time: 935ms
memory: 198920kb
input:
26
output:
808303766 820370175 298263490 679492153 641108688 746713355 193521815 743953067 918637561 801500615 153073374 942769296 737369646 737369646 942769296 153073374 801500615 918637561 743953067 193521815 746713355 641108688 679492153 298263490 820370175 808303766
result:
ok 26 lines
Test #25:
score: 0
Accepted
time: 975ms
memory: 198888kb
input:
27
output:
966093338 413577233 596032670 18588328 847446145 789982798 738899409 560228434 793194459 807183095 233296265 491027179 315239003 830332937 315239003 491027179 233296265 807183095 793194459 560228434 738899409 789982798 847446145 18588328 596032670 413577233 966093338
result:
ok 27 lines
Test #26:
score: 0
Accepted
time: 1021ms
memory: 211152kb
input:
279936
output:
290309878 660449178 855935767 911246480 412810579 495498459 666969537 815387077 839691467 778309397 809153859 251379794 979118403 658634705 532083804 535331397 650173235 904335123 103174052 244469968 106419566 205568916 604779076 913226092 698524092 856586660 390878718 396850634 777711099 244427127 ...
result:
ok 279936 lines
Test #27:
score: 0
Accepted
time: 960ms
memory: 199156kb
input:
28
output:
729403565 371366303 542574237 857872576 653455902 973702738 778528944 897834583 603048670 948653073 109571566 578653119 581413407 857242671 857242671 581413407 578653119 109571566 948653073 603048670 897834583 778528944 973702738 653455902 857872576 542574237 371366303 729403565
result:
ok 28 lines
Test #28:
score: 0
Accepted
time: 935ms
memory: 198952kb
input:
29
output:
196711083 13531060 101139289 140731236 472716702 123555148 613454502 628097252 705439510 101266132 448506542 770226037 67728891 755849630 702781856 755849630 67728891 770226037 448506542 101266132 705439510 628097252 613454502 123555148 472716702 140731236 101139289 13531060 196711083
result:
ok 29 lines
Test #29:
score: 0
Accepted
time: 1040ms
memory: 220240kb
input:
299961
output:
971184881 184588953 191428611 977547756 548569275 793431158 463365582 328308833 598523917 182127772 254275469 184707578 781558516 644523394 686845046 248494157 226721243 623572186 357789891 580841022 131140241 385918874 4920212 433630636 312269605 669886198 921361175 399335808 907757555 606626084 10...
result:
ok 299961 lines
Test #30:
score: 0
Accepted
time: 1058ms
memory: 219832kb
input:
299993
output:
177263178 50139253 256610050 316301693 115563089 859885869 870104658 826897459 292545986 248888417 414321895 974335763 341630065 881376964 217442612 408904167 98979347 777130329 397808289 278230868 769909571 169603631 214649864 539416828 301537535 592377704 864062984 365256440 10842833 245490662 699...
result:
ok 299993 lines
Test #31:
score: 0
Accepted
time: 957ms
memory: 198944kb
input:
3
output:
332748118 332748118 332748118
result:
ok 3 lines
Test #32:
score: 0
Accepted
time: 916ms
memory: 198888kb
input:
30
output:
460595366 652212370 803430084 661794231 634064869 787972038 909772705 983883425 903515619 122245837 470795197 167563267 954682487 119588183 851205676 851205676 119588183 954682487 167563267 470795197 122245837 903515619 983883425 909772705 787972038 634064869 661794231 803430084 652212370 460595366
result:
ok 30 lines
Test #33:
score: 0
Accepted
time: 1040ms
memory: 216496kb
input:
300000
output:
923211612 911921497 971364454 697145507 116463625 686356075 256581540 48117683 101227383 366373407 13332007 425925979 116072168 678177711 60481780 91274089 718407201 9296528 647070738 550032705 420919311 102535422 274664625 457580522 129361439 831068788 448567291 143239742 623580633 148707448 259250...
result:
ok 300000 lines
Test #34:
score: 0
Accepted
time: 946ms
memory: 198952kb
input:
31
output:
340838354 239734782 525707867 766578187 116505181 385351329 788635188 643717202 937460508 721713935 735497664 101999032 127561145 20853879 707624831 654107128 707624831 20853879 127561145 101999032 735497664 721713935 937460508 643717202 788635188 385351329 116505181 766578187 525707867 239734782 34...
result:
ok 31 lines
Test #35:
score: 0
Accepted
time: 951ms
memory: 198888kb
input:
32
output:
446031402 77687332 571473060 204956051 207560459 138303792 151985248 450677773 11873371 938502032 871515248 837132478 513791190 20115564 970998110 75985185 75985185 970998110 20115564 513791190 837132478 871515248 938502032 11873371 450677773 151985248 138303792 207560459 204956051 571473060 7768733...
result:
ok 32 lines
Test #36:
score: 0
Accepted
time: 961ms
memory: 198960kb
input:
33
output:
853106954 82880129 575520255 916721978 926678479 142419530 84682733 810452232 196094918 813878558 322466069 220687062 798047440 909169310 288008371 942489235 201791849 942489235 288008371 909169310 798047440 220687062 322466069 813878558 196094918 810452232 84682733 142419530 926678479 916721978 575...
result:
ok 33 lines
Test #37:
score: 0
Accepted
time: 899ms
memory: 198900kb
input:
34
output:
929394320 83492323 747053080 817319707 317953050 514423385 860784536 293530154 452140437 517689736 751658253 316564953 869784199 467888313 811485081 709030639 23129188 23129188 709030639 811485081 467888313 869784199 316564953 751658253 517689736 452140437 293530154 860784536 514423385 317953050 817...
result:
ok 34 lines
Test #38:
score: 0
Accepted
time: 938ms
memory: 198984kb
input:
35
output:
540654734 314626831 837624699 184323889 365872361 393930585 879195007 312574501 78708979 748581873 324293254 417136561 876592404 487791320 604806116 845266983 645767366 252903429 645767366 845266983 604806116 487791320 876592404 417136561 324293254 748581873 78708979 312574501 879195007 393930585 36...
result:
ok 35 lines
Test #39:
score: 0
Accepted
time: 924ms
memory: 198924kb
input:
36
output:
51081354 511574141 951867283 622313119 713247691 362013332 656643365 405095692 628825222 293991409 789092111 933741825 225955272 23800652 366821607 683578030 221593068 43841828 43841828 221593068 683578030 366821607 23800652 225955272 933741825 789092111 293991409 628825222 405095692 656643365 36201...
result:
ok 36 lines
Test #40:
score: 0
Accepted
time: 943ms
memory: 199152kb
input:
4
output:
748683265 748683265 748683265 748683265
result:
ok 4 lines
Test #41:
score: 0
Accepted
time: 929ms
memory: 199188kb
input:
5
output:
598946612 598946612 598946612 598946612 598946612
result:
ok 5 lines
Test #42:
score: 0
Accepted
time: 933ms
memory: 199192kb
input:
6
output:
166374059 166374059 166374059 166374059 166374059 166374059
result:
ok 6 lines
Test #43:
score: 0
Accepted
time: 956ms
memory: 198956kb
input:
7
output:
305019108 876236710 876236710 876236710 876236710 876236710 305019108
result:
ok 7 lines
Test #44:
score: 0
Accepted
time: 976ms
memory: 198952kb
input:
8
output:
64701023 112764640 160828257 160828257 160828257 160828257 112764640 64701023
result:
ok 8 lines
Test #45:
score: 0
Accepted
time: 955ms
memory: 199184kb
input:
9
output:
633145724 918754525 206118973 491727774 491727774 491727774 206118973 918754525 633145724
result:
ok 9 lines
Test #46:
score: 0
Accepted
time: 979ms
memory: 198884kb
input:
99
output:
739020504 312911963 432188234 902940408 183924030 408190957 451184416 406055830 303714508 823887354 684101558 806016717 606381407 410886174 925289875 754690209 401322124 486687944 211033111 566701375 920782017 235897531 887156376 808156217 44525905 736731698 943305762 131641799 248462913 939606622 4...
result:
ok 99 lines
Test #47:
score: 0
Accepted
time: 927ms
memory: 198916kb
input:
999
output:
914523111 7125756 633636252 126831023 107804652 471447506 426615280 775343316 119447489 265203812 403755774 947209157 436426971 17099897 585355295 319278422 43899419 148327785 593518343 710239085 27630589 230412089 177630810 362402141 107832678 155643425 922584474 765393615 488969743 322741275 58679...
result:
ok 999 lines
Test #48:
score: 0
Accepted
time: 951ms
memory: 199224kb
input:
9999
output:
154775049 250019430 274353493 830249076 623460301 666900681 108097268 880641375 920843819 72750241 503119772 979185294 695378287 300065112 985376707 114136761 996919342 779345278 727114830 39032304 301516045 2789877 589930780 388709635 257807541 222968825 620249279 367469083 108945138 547179552 6160...
result:
ok 9999 lines