QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #500146 | #7927. Fortune Telling | New_Folder | TL | 4535ms | 350372kb | C++14 | 2.2kb | 2024-07-31 23:16:23 | 2024-07-31 23:16:24 |
Judging History
answer
#pragma GCC optimize(2)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll mod = 998244353;
ll inv[7];
map<pair<int, int>, ll> dp;
ll fastpow(ll base,ll po){
ll ans = 1;
while(po){
if(po&1){
ans *= base;
ans %= mod;
}
base *= base;
base %= mod;
po >>=1;
}
return ans;
}
ll dfs(int n,int k){
if(n==0||k==0||n<k){
return 0;
}
if(!dp.count(make_pair(n,k))){
ll res;
if(n%6==0){
int bef = (k-1) % 6;
int af = 5 - bef;
res = (bef * dfs(5 * n / 6, k - k / 6 - (k % 6 == 0 ? 0 : 1)) + af * dfs(5 * n / 6, k - k / 6)) % mod * inv[6] % mod;
dp[make_pair(n, k)] = res;
return res;
}else{
int rem = n % 6;
if(k%6==0){
res = (rem * dfs(5 * n / 6, k - k / 6) + (5 - rem) * dfs(5 * n / 6 + 1, k - k / 6)) % mod * inv[6] % mod;
dp[make_pair(n, k)] = res;
}else{
int rem2 = k % 6;
if(rem>=rem2){
res = ((rem2 - 1) * dfs(5 * n / 6, k - k / 6 - 1) + (rem - rem2) * dfs(5 * n / 6, k - k / 6) + (6 - rem) * dfs(5 * n / 6 + 1, k - k / 6)) % mod * inv[6] % mod;
dp[make_pair(n, k)] = res;
}else{
res = ((rem)*dfs(5 * n / 6, k - k / 6 - 1) + (rem2 - rem - 1) * dfs(5 * n / 6 + 1, k - k / 6 - 1) + (6 - rem2) * dfs(5 * n / 6 + 1, k - k / 6)) % mod * inv[6] % mod;
dp[make_pair(n, k)] = res;
}
}
return res;
}
}else{
return dp[make_pair(n, k)];
}
}
void solve()
{
int n;
cin >> n;
for (int i = 1; i <= 6;i++){
inv[i] = fastpow(i * 1LL, mod - 2);
}
for (int i = 1; i <= 6; i++)
{
for (int j = 1; j <= i; j++)
{
dp[make_pair(i, j)] = inv[i];
}
}
for (int k = 1; k <= n;k++){
cout << dfs(n, k) << '\n';
}
}
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3608kb
input:
3
output:
332748118 332748118 332748118
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
7
output:
305019108 876236710 876236710 876236710 876236710 876236710 305019108
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
8
output:
64701023 112764640 160828257 160828257 160828257 160828257 112764640 64701023
result:
ok 8 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
10
output:
409773145 853745402 299473306 743445563 189173467 189173467 743445563 299473306 853745402 409773145
result:
ok 10 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
11
output:
989514850 873566509 757618168 641669827 525721486 409773145 525721486 641669827 757618168 873566509 989514850
result:
ok 11 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3588kb
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: 0ms
memory: 3648kb
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: 2001ms
memory: 169820kb
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: 0ms
memory: 3580kb
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: 0ms
memory: 3640kb
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: 0ms
memory: 3656kb
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: 0ms
memory: 3560kb
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: 1ms
memory: 3640kb
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: 0ms
memory: 3636kb
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: 0ms
memory: 3636kb
input:
2
output:
499122177 499122177
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 0ms
memory: 3592kb
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: 0ms
memory: 3564kb
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: 0ms
memory: 3700kb
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: 3950ms
memory: 312976kb
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: 1ms
memory: 3592kb
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: 1ms
memory: 3628kb
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: 0ms
memory: 3704kb
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: 4535ms
memory: 350372kb
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: 1ms
memory: 3724kb
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: 0ms
memory: 3640kb
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: 1885ms
memory: 186804kb
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: 1ms
memory: 3648kb
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: 1ms
memory: 3664kb
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: -100
Time Limit Exceeded
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...