QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#614871#9436. Some Sum of Subsetucup-team3282#WA 1775ms244416kbC++201.5kb2024-10-05 17:04:032024-10-05 17:04:07

Judging History

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

  • [2024-10-05 17:04:07]
  • 评测
  • 测评结果:WA
  • 用时:1775ms
  • 内存:244416kb
  • [2024-10-05 17:04:03]
  • 提交

answer

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
const long long mod=998244353;
long long ans[5050];
long long dp[5050][5050];
long long x[5050];
long long cnt[5050][5050];
long long n,m;
long long pow(long long a,long long b=mod-2){
    if(b==1)return a;
    long long ret=pow(a,b>>1);
    if(b&1)return ret*ret%mod*a%mod;
    else return ret*ret%mod;
}
bool cmp(long long a,long long b){
    return a>b;
}
int main(){
    // cout<<30ll*pow(6)%mod;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x[i];
    }
    sort(x+1,x+n+1,cmp);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3005;j++)dp[i][j]=dp[i-1][j];
        if(x[i]<m)dp[i][x[i]]++;
        else ans[n-i]++;
        for(int j=1;j<=3005;j++){
            if(j+x[i]>=m)ans[n-i]+=dp[i-1][j];
            else{
                dp[i][j+x[i]]+=dp[i-1][j];
            }
        }
    }
    cnt[0][0]=1;
    for(int i=0;i<=n;i++){
        cnt[i][0]=1;
        for(int k=1;k<=n;k++){
            cnt[i][k]=(cnt[i][k-1]*pow(k)%mod*(i-k+1))%mod;
        }
        for(int k=n;k>=0;k--){
            cnt[i][k]=(cnt[i][k]+cnt[i][k+1])%mod;
        }
    }
    // for(int i=0;i<=n;i++){
    //     cout<<ans[i]<<endl;
    // }
    // cout<<endl;
    for(int k=0;k<=n;k++){
        long long anser=0;
        for(int i=k;i<=n;i++){
            anser=(anser+(ans[i]*cnt[i][k]))%mod;
        }
        cout<<anser<<endl;
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5632kb

input:

4 7
3 1 5 2

output:

6
4
1
0
0

result:

ok 5 tokens

Test #2:

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

input:

1 5
7

output:

1
0

result:

ok 2 tokens

Test #3:

score: 0
Accepted
time: 1ms
memory: 7736kb

input:

9 18
1 9 5 6 2 7 1 4 8

output:

346
309
230
126
46
10
1
0
0
0

result:

ok 10 tokens

Test #4:

score: 0
Accepted
time: 1ms
memory: 5600kb

input:

1 1467
556

output:

0
0

result:

ok 2 tokens

Test #5:

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

input:

1 1753
2514

output:

1
0

result:

ok 2 tokens

Test #6:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

1 1182
1182

output:

1
0

result:

ok 2 tokens

Test #7:

score: 0
Accepted
time: 1ms
memory: 5752kb

input:

2 1741
955 835

output:

1
0
0

result:

ok 3 tokens

Test #8:

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

input:

2 1481
2004 1570

output:

3
1
0

result:

ok 3 tokens

Test #9:

score: 0
Accepted
time: 1ms
memory: 5604kb

input:

2 1336
1336 1336

output:

3
1
0

result:

ok 3 tokens

Test #10:

score: 0
Accepted
time: 1ms
memory: 5788kb

input:

12 400
2163 2729 1322 2787 2404 1068 1502 746 898 2057 1771 502

output:

4095
4083
4017
3797
3302
2510
1586
794
299
79
13
1
0

result:

ok 13 tokens

Test #11:

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

input:

42 1609
532 722 2650 2889 2260 659 1831 401 2779 1262 2185 1479 515 552 1627 637 1080 580 1589 2154 2650 219 2924 1712 311 2609 1062 968 1357 1310 1942 2419 2465 300 2546 2537 2967 1197 2271 1551 999 2531

output:

780135870
780135476
780133126
780115746
779984839
779086101
773744618
746617208
628409426
182368401
707355349
419830171
342550392
778349940
825220795
979080057
177969332
68371210
748001250
187917550
492152134
287983982
592218358
32133349
711757614
602140473
799225822
952989153
1466429
437088327
3596...

result:

ok 43 tokens

Test #12:

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

input:

93 24
1687 2324 1216 2696 2884 1678 1301 1957 1247 526 2519 2252 2141 960 1505 175 315 388 440 892 837 1942 256 1667 641 1629 2565 2837 1200 2427 418 1072 427 1589 969 886 2991 2249 539 1132 949 2425 2616 2107 1259 582 1979 386 177 1860 2825 316 2004 956 1218 2332 1498 2939 1126 1706 404 1604 505 11...

output:

958346177
958346084
958341806
958212040
955292305
903321022
141075538
649896624
629379357
102857051
471642575
350313411
852223261
984774652
743966819
740155079
222450670
637406264
282036249
875748580
177575581
602719974
451360351
244531346
556337405
139169356
737451056
595307440
402860967
935337558
...

result:

ok 94 tokens

Test #13:

score: 0
Accepted
time: 9ms
memory: 18008kb

input:

162 1057
695 2739 2637 797 503 1051 2243 2429 160 1900 1798 1584 1488 1377 2764 1324 978 2696 913 2651 817 1522 819 314 882 1536 2785 2193 540 2417 1357 959 2765 408 1693 1305 1643 2565 2677 966 860 2547 936 2123 496 2098 2130 38 378 1395 2725 2657 2107 2096 2039 2421 2548 431 2205 2907 1085 2919 25...

output:

389411124
389407419
389358436
388250937
356407046
445051896
284078655
310513451
444646929
152850475
993044643
431761154
990006065
274011210
363632851
570583138
738018586
406619069
554524447
68656757
468185513
297611934
115797909
686917345
226595373
291150212
272381264
220037421
897019520
543603827
1...

result:

ok 163 tokens

Test #14:

score: 0
Accepted
time: 19ms
memory: 26360kb

input:

258 115
711 2524 2720 190 2722 285 1451 2274 729 433 2198 1787 1513 1943 656 691 1564 110 857 1604 1900 749 936 811 736 2934 160 2765 1024 2777 1176 2451 1358 1527 207 2142 564 766 2187 1122 2394 2701 1518 1871 2047 192 448 198 1178 2337 2187 197 958 2712 1792 1801 2125 1553 642 991 2419 765 556 667...

output:

679628095
679627797
679594544
676765332
496412885
318714207
312586022
91966775
656865481
43835426
451822313
302874781
814080325
198066519
398512797
65425915
372232292
981614918
489120129
415216968
680055200
354073986
472346737
340468228
671304901
14537393
732660445
322180935
429580213
661767647
3710...

result:

ok 259 tokens

Test #15:

score: 0
Accepted
time: 22ms
memory: 34364kb

input:

361 2442
2259 2509 1332 1972 2038 20 69 2957 2994 1239 14 2165 1513 1687 110 296 1198 2179 2383 1107 1399 1283 2159 763 1797 2429 700 716 2155 1675 1084 1240 2511 88 2850 2095 1991 528 2350 2944 2478 1551 2603 1718 1997 2358 829 298 147 559 361 1147 1502 92 1500 2718 875 1138 681 1450 2527 2048 2358...

output:

307302301
580505153
851886546
949704794
513166194
554298173
376814448
260998744
286352570
1306229
942623010
990880004
483637443
639566802
87384186
647331744
456851473
79181365
814841605
928484866
732051628
807565561
967052391
396403870
827423238
628292032
729375608
76807794
441407519
105436762
37817...

result:

ok 362 tokens

Test #16:

score: 0
Accepted
time: 43ms
memory: 46748kb

input:

494 1465
2911 1256 1749 2495 1360 2696 1542 1925 2771 2971 2000 2177 522 1459 2923 1376 2910 871 2813 118 916 2732 505 2715 1867 1643 410 2611 1509 450 2216 2977 2146 25 2867 1921 1463 1404 1506 1642 1374 440 1367 746 773 1583 1189 88 138 206 333 95 2679 1798 1833 1574 269 261 2637 339 2942 880 1946...

output:

601338713
71190482
366743920
29439076
165764717
623413052
621710375
186270648
164229544
245356732
574049815
159928423
293955886
283917475
710614042
644889770
525216501
408416510
614685151
855141118
684389723
48613954
630787816
206430371
603047420
232394421
191648298
41682916
532845844
896480859
5580...

result:

ok 495 tokens

Test #17:

score: 0
Accepted
time: 89ms
memory: 55256kb

input:

641 1482
2059 104 2948 2452 980 1208 2490 1732 1157 933 1474 2562 2837 1879 781 1184 1315 1945 1354 1998 2342 1912 244 671 2332 1838 1982 255 559 523 2656 903 1703 97 368 278 709 2032 627 2965 2324 179 188 799 2729 960 2861 2792 1750 2827 158 1526 856 1772 1347 468 1497 2721 1521 2639 178 906 1406 9...

output:

954243398
984112835
721285238
517568578
548377046
81412459
964922628
162381954
804965567
248085717
497009368
165592753
403723827
130398680
814606186
255490452
680764934
37801227
440785027
805711271
661503649
155012433
312914255
502270457
953130944
352520788
354510603
848312651
602873666
106063941
11...

result:

ok 642 tokens

Test #18:

score: 0
Accepted
time: 131ms
memory: 71484kb

input:

813 853
791 1331 2436 2101 1358 2069 418 2806 362 1808 577 604 2470 1376 72 143 2920 1225 2844 2046 2642 1973 1833 367 2851 1999 1771 1892 475 657 1218 875 2530 2161 1359 2556 1426 168 198 1095 1887 496 1567 840 1635 1534 2968 414 1332 2129 2023 509 2460 2517 642 1601 891 207 557 1332 1762 2531 2185...

output:

266757501
960695671
105371913
284228297
767246574
537963296
132439517
656989604
183994944
35050045
737170898
815660864
387545312
294470919
26759305
981025679
347289315
388903831
740619964
67226751
848226762
170823914
800033200
107985190
574075391
904477100
183572348
259260214
687334926
705536921
403...

result:

ok 814 tokens

Test #19:

score: 0
Accepted
time: 198ms
memory: 85624kb

input:

1007 11
1548 2721 289 1606 1776 885 210 2105 1488 2220 2135 2 1303 2585 59 531 2959 1683 2201 2952 2721 2156 1426 2042 1897 1025 880 2091 2934 1677 472 659 2605 946 1221 2622 948 567 1606 2347 245 775 1505 2618 421 1391 588 2180 608 647 644 2828 1413 2458 1731 2480 4 2363 32 995 2458 470 2133 2117 2...

output:

976474719
976473708
975967181
806282650
141727206
396996576
102471855
909943074
22921318
389697349
458201923
133244365
114364582
665823743
887894407
16360457
884694972
181985551
464497163
616618136
744385990
760009010
189711548
244790462
506537230
895836166
625692223
792905824
655915741
643896846
25...

result:

ok 1008 tokens

Test #20:

score: 0
Accepted
time: 1775ms
memory: 244300kb

input:

3000 1
1355 1270 1449 1697 714 2076 2157 2727 2019 1150 1209 1945 2851 36 1944 2693 2551 2030 1528 2375 1412 901 2384 1137 2050 1760 2172 1466 2336 2282 591 1692 2162 19 2748 354 2203 1523 2758 334 2866 2014 2612 1212 1305 1533 1771 1054 1613 1324 2344 361 2394 421 871 1544 2235 1457 1407 2015 811 1...

output:

21292721
21289721
16791221
512511986
334834758
882434382
706960640
665267230
289946597
408147435
224519114
586218366
171985713
563297430
556437524
322202503
857434290
90581997
615019010
962912804
9356526
503947387
457550366
396208967
398932791
403738607
32178535
329319256
898069998
426487055
9319434...

result:

ok 3001 tokens

Test #21:

score: 0
Accepted
time: 1759ms
memory: 244084kb

input:

3000 1
1921 2368 2560 1531 627 323 582 1630 1207 1803 2909 2609 424 2079 2814 1223 1098 1692 2814 655 2743 534 1681 2935 2280 396 311 2337 2351 995 2296 1772 2292 1799 2183 2258 1880 2097 660 1430 1177 1786 2990 2274 2140 1640 1874 2755 2968 2926 2657 667 330 1998 1282 1199 663 525 2192 2375 595 120...

output:

21292721
21289721
16791221
512511986
334834758
882434382
706960640
665267230
289946597
408147435
224519114
586218366
171985713
563297430
556437524
322202503
857434290
90581997
615019010
962912804
9356526
503947387
457550366
396208967
398932791
403738607
32178535
329319256
898069998
426487055
9319434...

result:

ok 3001 tokens

Test #22:

score: 0
Accepted
time: 1751ms
memory: 241512kb

input:

3000 1
3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 3000 300...

output:

21292721
21289721
16791221
512511986
334834758
882434382
706960640
665267230
289946597
408147435
224519114
586218366
171985713
563297430
556437524
322202503
857434290
90581997
615019010
962912804
9356526
503947387
457550366
396208967
398932791
403738607
32178535
329319256
898069998
426487055
9319434...

result:

ok 3001 tokens

Test #23:

score: 0
Accepted
time: 1761ms
memory: 244044kb

input:

3000 2
2929 1694 2047 2024 2843 705 2906 897 1799 823 387 1241 1146 818 120 898 898 1602 2514 2430 1203 1900 708 391 1083 74 2739 1695 197 349 947 886 2232 1458 1520 2626 1612 2828 191 2345 1620 1186 2377 1126 1152 285 1746 233 754 800 2355 2677 242 811 240 2887 2329 1366 1822 1307 1711 1697 437 248...

output:

21292720
21289721
16791221
512511986
334834758
882434382
706960640
665267230
289946597
408147435
224519114
586218366
171985713
563297430
556437524
322202503
857434290
90581997
615019010
962912804
9356526
503947387
457550366
396208967
398932791
403738607
32178535
329319256
898069998
426487055
9319434...

result:

ok 3001 tokens

Test #24:

score: 0
Accepted
time: 1762ms
memory: 242628kb

input:

3000 3
1990 1915 1351 1338 2134 66 2574 2191 2993 1249 596 195 2950 2009 1794 1188 1960 1864 30 1122 1642 2650 2578 819 1948 831 1659 62 205 1346 1466 792 2453 316 1284 552 858 4 686 257 2207 2550 1714 1601 525 2804 997 2229 2662 2478 1692 2318 1087 444 1911 1623 2880 2688 2184 2360 1168 1544 2380 1...

output:

21292719
21289720
16791221
512511986
334834758
882434382
706960640
665267230
289946597
408147435
224519114
586218366
171985713
563297430
556437524
322202503
857434290
90581997
615019010
962912804
9356526
503947387
457550366
396208967
398932791
403738607
32178535
329319256
898069998
426487055
9319434...

result:

ok 3001 tokens

Test #25:

score: 0
Accepted
time: 1759ms
memory: 244036kb

input:

3000 3000
3000 2998 3000 3000 3000 2999 3000 2999 2999 3000 2998 3000 2998 3000 2999 2999 2998 2998 3000 3000 2999 2999 3000 2999 2998 2999 2998 3000 2998 3000 2998 3000 3000 2999 2998 3000 3000 2998 3000 2999 2998 2999 3000 3000 3000 3000 2998 3000 2999 2999 3000 2998 2998 2999 3000 2999 3000 3000 ...

output:

21290734
19316630
707751382
830938763
444808297
608067155
924094933
1687509
563478752
607612632
590805700
341252112
889244077
874047101
768557604
511649185
332247409
288135972
282335483
769619655
538126159
476242053
130441813
746797303
734952758
497061337
857679746
216231552
246511085
759366222
3825...

result:

ok 3001 tokens

Test #26:

score: 0
Accepted
time: 1767ms
memory: 244416kb

input:

3000 3000
2999 2996 2999 3000 2996 2996 3000 2998 3000 2997 2999 3000 3000 2998 2999 2997 3000 2998 3000 2998 3000 2999 2996 2999 2997 2999 3000 3000 2997 2996 2997 2998 2999 3000 2996 2997 3000 2999 2999 2996 2998 2996 2997 2999 2997 2997 3000 3000 2996 2999 2997 2998 2999 3000 2996 2998 3000 2996 ...

output:

21290331
18434866
739059700
35105245
515348178
762925416
648427163
574103402
785280827
554393944
104625284
276008864
634589346
174178635
811170282
575152487
185638621
202892992
660739128
94093369
640462044
37424106
905890057
815740004
612803528
929501183
146372729
197959531
663401476
725068210
36001...

result:

ok 3001 tokens

Test #27:

score: -100
Wrong Answer
time: 1763ms
memory: 243860kb

input:

3000 2999
571 2015 316 840 560 1948 2355 2589 597 1002 2932 627 472 1205 428 2799 1633 2092 2473 719 428 1821 773 1208 103 227 2661 1734 665 1200 1907 920 2002 2912 2112 2779 91 175 1118 1710 2929 844 598 2586 413 2147 1992 199 2633 2460 1677 326 1819 2809 2567 565 572 2166 1358 2672 2754 1347 699 1...

output:

988469636
626562568
68910180
488669980
215636641
539223893
519289148
868567747
841877259
355827433
818845456
664372154
471091530
849478071
4353523
774914501
333642457
636783437
559877147
252547901
580080920
755788020
220059574
911887559
313269054
884129728
948988063
990164459
362918885
29704727
5590...

result:

wrong answer 1st words differ - expected: '126306401', found: '988469636'