QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#500513#7927. Fortune TellingNew_FolderAC ✓64ms69656kbC++233.4kb2024-08-01 13:25:122024-08-01 13:25:13

Judging History

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

  • [2024-08-01 13:25:13]
  • 评测
  • 测评结果:AC
  • 用时:64ms
  • 内存:69656kb
  • [2024-08-01 13:25:12]
  • 提交

answer

#pragma GCC optimize(2)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll mod = 998244353;
ll inv[7];
//vector<unordered_map<int, ll>> dp;
vector<vector<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;
}
void calc(int n){
    dp[n].resize(n + 1);
    if(dp[5*n/6].empty()){
        calc(5 * n / 6);
    }
    if(dp[5*n/6+1].empty()){
        calc(5 * n / 6 + 1);
    }
    for (int k = 1; k <= n;k++){
        ll res = 0;
        if (n % 6 == 0)
        {
            int bef = (k - 1) % 6;
            int af = 5 - bef;
            if (bef)
            {
                res += bef * dp[5 * n / 6][ k - k / 6 - (k % 6 == 0 ? 0 : 1)];
            }
            if (af)
            {
                res += af * dp[5 * n / 6][ k - k / 6];
            }
            res = res % mod * inv[6] % mod;
            dp[n][k] = res;
        }
        else
        {
            int rem = n % 6;
            if (k % 6 == 0)
            {
                if (rem)
                {
                    res += rem * dp[5 * n / 6][ k - k / 6];
                }
                if (5 - rem)
                {
                    res += (5 - rem) * dp[5 * n / 6 + 1][ k - k / 6];
                }
                res = res % mod * inv[6] % mod;
                dp[n][k] = res;
            }
            else
            {
                int rem2 = k % 6;
                if (rem >= rem2)
                {
                    if (rem2 - 1)
                    {
                        res += (rem2 - 1) * dp[5 * n / 6][ k - k / 6 - 1];
                    }
                    if (rem - rem2)
                    {
                        res += (rem - rem2) * dp[5 * n / 6][ k - k / 6];
                    }
                    if (6 - rem)
                    {
                        res += (6 - rem) * dp[5 * n / 6 + 1][ k - k / 6];
                    }
                    res = res % mod * inv[6] % mod;
                    dp[n][k] = res;
                }
                else
                {
                    if (rem)
                    {
                        res += (rem)*dp[5 * n / 6][ k - k / 6 - 1];
                    }
                    if (rem2 - rem - 1)
                    {
                        res += (rem2 - rem - 1) * dp[5 * n / 6 + 1][ k - k / 6 - 1];
                    }
                    if (6 - rem2)
                    {
                        res += (6 - rem2) * dp[5 * n / 6 + 1][k - k / 6];
                    }
                    res = res % mod * inv[6] % mod;
                    dp[n][k] = res;
                }
            }
        }
    }
}
void solve()
{
    int n;
    cin >> n;
    dp.resize(max(7,n+1));
    for (int i = 1; i <= 6;i++){
        inv[i] = fastpow(i * 1LL, mod - 2);
    }
    for (int i = 1; i <= 6; i++)
    {
        dp[i].resize(i + 1);
        for (int j = 1; j <= i; j++)
        {
            dp[i][j] = inv[i];
        }
    }
    calc(n);
    for (int i = 1; i <= n;i++){
        cout << dp[n][i] << '\n';
    }
    //cout << "finish" << endl;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3556kb

input:

3

output:

332748118
332748118
332748118

result:

ok 3 lines

Test #2:

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

input:

7

output:

305019108
876236710
876236710
876236710
876236710
876236710
305019108

result:

ok 7 lines

Test #3:

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

input:

8

output:

64701023
112764640
160828257
160828257
160828257
160828257
112764640
64701023

result:

ok 8 lines

Test #4:

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

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: 3580kb

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: 3556kb

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: 3616kb

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: 21ms
memory: 30212kb

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: 3556kb

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: 3644kb

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: 3560kb

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: 3624kb

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: 3628kb

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: 3644kb

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: 3580kb

input:

2

output:

499122177
499122177

result:

ok 2 lines

Test #16:

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

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: 3580kb

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: 3644kb

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: 46ms
memory: 53428kb

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: 0ms
memory: 3632kb

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: 0ms
memory: 3640kb

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: 3612kb

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: 42ms
memory: 55180kb

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: 0ms
memory: 3612kb

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: 3584kb

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: 32ms
memory: 43792kb

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: 0ms
memory: 3616kb

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: 0ms
memory: 3624kb

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: 56ms
memory: 68164kb

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: 58ms
memory: 69656kb

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: 0ms
memory: 3580kb

input:

3

output:

332748118
332748118
332748118

result:

ok 3 lines

Test #32:

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

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: 64ms
memory: 63868kb

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: 0ms
memory: 3556kb

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: 0ms
memory: 3560kb

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: 0ms
memory: 3648kb

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: 0ms
memory: 3612kb

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: 0ms
memory: 3708kb

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: 0ms
memory: 3616kb

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: 0ms
memory: 3560kb

input:

4

output:

748683265
748683265
748683265
748683265

result:

ok 4 lines

Test #41:

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

input:

5

output:

598946612
598946612
598946612
598946612
598946612

result:

ok 5 lines

Test #42:

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

input:

6

output:

166374059
166374059
166374059
166374059
166374059
166374059

result:

ok 6 lines

Test #43:

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

input:

7

output:

305019108
876236710
876236710
876236710
876236710
876236710
305019108

result:

ok 7 lines

Test #44:

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

input:

8

output:

64701023
112764640
160828257
160828257
160828257
160828257
112764640
64701023

result:

ok 8 lines

Test #45:

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

input:

9

output:

633145724
918754525
206118973
491727774
491727774
491727774
206118973
918754525
633145724

result:

ok 9 lines

Test #46:

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

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: 0ms
memory: 3816kb

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: 0ms
memory: 5560kb

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