QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #292884 | #7927. Fortune Telling | mendicillin2# | TL | 4767ms | 313236kb | C++17 | 1.1kb | 2023-12-28 16:09:29 | 2023-12-28 16:09:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
inline int power(int x,int y)
{
int ans=1;
for(;y;y>>=1)
{
if(y&1) ans=ans*x%mod;
x=x*x%mod;
}
return ans;
}
int n;
map<int,int> mp;
int inv[15];
inline int ask(int x,int k)
{
return (x-1)*n+k;
}
inline int Work(int n,int k)
{
if(n==1) return 1;
if(mp.find(ask(n,k))!=mp.end()) return mp[ask(n,k)];
if(n<=6)
{
int ans=0;
for(int i=1;i<=n;i++)
{
if(i%6==k%6) continue;
ans=(ans+Work(n-1,k-(i<k)))%mod;
}
return mp[ask(n,k)]=ans*inv[n]%mod;
}
int ans=0;
for(int i=1;i<=6;i++)
{
if(i%6==k%6) continue;
ans=(ans+Work(n-(n-i)/6-(i<=n),k-(k-i)/6-(i<=k)))%mod;
}
return mp[ask(n,k)]=ans*inv[6]%mod;
}
signed main()
{
n=read();
for(int i=1;i<=6;i++) inv[i]=power(i,mod-2);
for(int i=1;i<=n;i++) printf("%lld\n",Work(n,i));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3888kb
input:
3
output:
332748118 332748118 332748118
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
7
output:
305019108 876236710 876236710 876236710 876236710 876236710 305019108
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
8
output:
64701023 112764640 160828257 160828257 160828257 160828257 112764640 64701023
result:
ok 8 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3824kb
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: 3808kb
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: 3860kb
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: 3892kb
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: 2335ms
memory: 170068kb
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: 1ms
memory: 3952kb
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: 3864kb
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: 3900kb
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: 1ms
memory: 3776kb
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: 0ms
memory: 3864kb
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: 3772kb
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: 3820kb
input:
2
output:
499122177 499122177
result:
ok 2 lines
Test #16:
score: 0
Accepted
time: 0ms
memory: 3776kb
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: 3872kb
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: 3780kb
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: 4767ms
memory: 313236kb
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: 3868kb
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: 3792kb
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: 1ms
memory: 3860kb
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: -100
Time Limit Exceeded
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...