QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#734211 | #9486. Random Mex | ucup-team3215 | AC ✓ | 229ms | 254076kb | C++23 | 927b | 2024-11-11 05:41:19 | 2024-11-11 05:41:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 998244353;
constexpr int N = 8005;
ll fact[N];
int S[N][N];
ll modPow(ll x, ll n) {
if (!n)return 1;
ll u = modPow(x, n / 2);
u = u * u % mod;
if (n % 2) u = u * x % mod;
return u;
}
void solve(){
ll n,m;cin >> n >> m;
ll total = modPow(m + 1,n);
total -= modPow(m,n);
total -=fact[m + 1] * S[n][m+1]%mod;
total %=mod;
if(total < 0)total += mod;
cout << total * modPow(modPow(m,n),mod - 2)%mod << "\n";
}
int main() {
cin.tie(0)->sync_with_stdio(false);
S[0][0] = 1;
for (ll n = 1; n < N; ++n) {
for (ll k = 1; k <= n; ++k) {
S[n][k] = (S[n - 1][k] * k + S[n - 1][k - 1]) % mod;
}
}
fact[0]=1;for(ll i = 1;i < N;++i)fact[i] = i * fact[i-1]%mod;
int t;
cin >> t;
while (t--)solve();
}
详细
Test #1:
score: 100
Accepted
time: 48ms
memory: 253660kb
input:
4 3 2 1 1 20 23 8000 8000
output:
374341634 1 111675632 994279778
result:
ok 4 tokens
Test #2:
score: 0
Accepted
time: 44ms
memory: 254076kb
input:
5 60 26 33 95 18 89 82 12 77 36
output:
945602338 254913692 403396795 820508695 360125985
result:
ok 5 tokens
Test #3:
score: 0
Accepted
time: 59ms
memory: 253180kb
input:
5 23 13 95 8 73 19 72 74 23 51
output:
788774542 935467825 483603650 274447212 738760583
result:
ok 5 tokens
Test #4:
score: 0
Accepted
time: 24ms
memory: 253324kb
input:
5 7 79 47 12 64 29 23 59 88 21
output:
238359778 424364643 993714623 760177301 865871793
result:
ok 5 tokens
Test #5:
score: 0
Accepted
time: 36ms
memory: 252792kb
input:
5 39 47 22 33 2 58 43 45 32 67
output:
68068469 21035974 735626561 965644028 137192045
result:
ok 5 tokens
Test #6:
score: 0
Accepted
time: 44ms
memory: 253904kb
input:
5 57 73 20 64 18 72 56 64 9 58
output:
218207240 814770590 121270366 636721674 420274847
result:
ok 5 tokens
Test #7:
score: 0
Accepted
time: 39ms
memory: 252548kb
input:
5 100 100 100 99 99 100 98 99 99 97
output:
585389012 131732771 619127511 549657738 490584077
result:
ok 5 tokens
Test #8:
score: 0
Accepted
time: 46ms
memory: 253392kb
input:
1922 4663 5021 7459 306 3249 6943 4902 4260 6118 5364 4997 7021 6772 3346 3916 7327 7156 4792 1228 5381 3240 7026 131 5713 1120 5334 2186 610 7638 2846 891 6274 5363 426 1335 7417 2127 396 323 7781 5435 1922 4989 5238 2886 3788 5413 1384 7624 4245 7191 6758 7755 5835 7660 1787 1043 7586 803 7889 79 ...
output:
672342508 406758717 456109836 583347519 254351863 547587964 177045319 935533988 555369350 136991350 790497273 429246740 670208582 782070778 169184793 771435402 251034885 528072506 303570823 257245963 629853925 267752975 350150586 786769060 44222606 607226242 320315817 861879910 752261031 341472947 2...
result:
ok 1922 tokens
Test #9:
score: 0
Accepted
time: 52ms
memory: 252720kb
input:
1569 1690 3118 4489 1453 6866 3161 6664 1290 2600 7962 6689 4642 522 772 2162 4794 3190 5987 3327 4938 6130 3823 6941 5425 3091 6213 3025 388 5330 3690 3161 6492 1740 5873 5530 1458 2496 6781 6287 5635 662 3877 3505 5138 2511 2028 3500 859 7572 813 2520 3943 7377 4768 6158 1882 7427 1702 4296 5159 5...
output:
786392950 680031668 677629004 801851613 786349751 79816839 959519914 318092993 339917671 724667845 890615671 100962701 589915015 941504560 820459949 486565344 823734064 220460851 576680186 554430485 361102164 218914963 840663949 777667686 736007308 919520675 863371619 66677855 637862969 67422276 384...
result:
ok 1569 tokens
Test #10:
score: 0
Accepted
time: 40ms
memory: 252520kb
input:
1181 4017 5052 5241 7494 7719 3875 7903 143 7280 2239 6098 2785 4900 5047 3542 4892 3011 430 4358 3184 1473 1501 2732 5656 6806 7106 6079 4418 4893 233 1746 3558 3801 650 4506 970 7836 5225 1970 1822 3342 7672 3519 1017 6258 3172 6871 3994 4143 3721 1752 2936 5806 2553 1727 3701 6464 2302 2048 3091 ...
output:
648881231 526073149 469264135 392921762 374237236 765018788 699026377 457948355 693169225 754094043 700515631 122741833 428610910 661965148 268857241 313001621 686530925 177273994 339148514 571456944 973936686 176745436 23414882 360870357 623038194 895354617 386646311 288047747 236022755 955017813 1...
result:
ok 1181 tokens
Test #11:
score: 0
Accepted
time: 59ms
memory: 253952kb
input:
1080 7499 4465 5556 2341 808 1986 3404 6901 4609 4168 235 5744 5131 7261 6616 1993 4624 3943 5843 6392 4889 2743 386 6670 1188 23 4216 4225 1193 1295 6097 4160 710 2728 7146 4193 5425 4148 6206 7462 7147 1808 2381 1254 4193 1297 1359 233 991 6979 5009 6963 1824 2135 1078 6208 2893 5858 320 4173 4937...
output:
584491148 616649457 512306930 528213999 550156793 344729669 779502829 828764040 365090398 371482124 273983459 617971432 137019685 400487464 761520033 143391408 908639433 294086517 926654429 723576006 993426946 572674399 178336952 402120004 148856064 897242602 390050708 850225145 605879501 962941650 ...
result:
ok 1080 tokens
Test #12:
score: 0
Accepted
time: 54ms
memory: 253088kb
input:
1534 2137 7885 2676 2513 53 3021 1623 5195 660 4999 2881 7697 6034 6429 4724 4014 5986 266 7826 726 4086 6628 7498 6114 4801 4415 5037 4206 700 6054 3497 476 1715 5892 6009 6340 1251 2345 2819 4107 7544 864 3138 4179 3909 912 180 4496 4727 2930 1057 7077 4123 2560 4963 4100 7118 463 2945 935 6573 41...
output:
676937061 816416208 899106800 778722088 621854770 637694747 789726622 647248717 143759992 290955099 204045987 17260543 508242895 836696138 605720517 462338702 426815143 443255417 341689094 660082176 461660684 531200268 467927798 816405934 307396775 786033585 765478425 774747686 67909522 155061063 47...
result:
ok 1534 tokens
Test #13:
score: 0
Accepted
time: 212ms
memory: 253180kb
input:
300000 1983 855 7767 4477 6925 7526 7306 5358 3987 46 5716 3789 4487 4391 4358 7525 933 1015 953 546 5716 5487 968 6561 2932 6558 6796 1429 4864 4211 5955 4414 6657 5171 2784 3725 1139 7304 553 3163 7248 6772 1977 6216 4701 7267 6130 4055 5688 1364 1335 4326 2633 3945 7851 5521 6474 2532 6869 5201 2...
output:
917986185 514093688 240004856 10138263 106086887 486293160 462563200 380236329 178495199 768072852 293049871 679765965 19413063 914310451 303877752 97576016 551398628 294935753 497649688 625770227 916721949 945723005 793837895 598750153 811171822 281042931 224310375 229099648 232754408 173968951 334...
result:
ok 300000 tokens
Test #14:
score: 0
Accepted
time: 220ms
memory: 254016kb
input:
300000 6276 3969 1337 287 69 4971 4553 4420 4304 107 836 5154 7039 7495 4074 5597 3321 6214 5997 5958 1357 67 5347 5263 5228 5204 6067 7567 3498 226 1830 3989 7897 3908 4547 714 1973 4138 3392 2046 6781 2623 7423 7027 3219 1631 688 6768 1270 5667 1911 1106 4914 755 4060 6194 5588 6416 5379 3593 4950...
output:
785609765 389521714 617648697 133397962 663080285 932116327 864145458 250419436 926868327 231968290 706343931 34357834 259117474 30429506 802394434 962282557 421143424 325071266 930611818 413209658 588520237 879895836 293550595 779472804 703506662 997419552 167326709 571013401 948481475 873418350 52...
result:
ok 300000 tokens
Test #15:
score: 0
Accepted
time: 202ms
memory: 253844kb
input:
300000 172 7671 2377 1841 772 2572 897 2774 7862 7766 563 7835 50 5627 3975 332 3125 4092 6642 7913 377 4237 5378 2346 7235 484 7254 4026 5032 189 698 3244 5656 1277 42 5418 294 7339 6054 5619 5273 6487 3381 4739 1652 5241 5455 6606 5194 1556 2248 5307 6266 94 6669 4982 4033 4379 6666 4863 7785 583 ...
output:
690315780 651031191 910258157 142140073 777756320 339555304 856925271 481764268 804784924 892959827 162363106 880216583 28750709 919204633 590976688 235862971 115143352 552437269 440186544 342438715 203287097 208201535 473851494 630433067 795957931 121121486 655185544 120192487 18559533 512410924 14...
result:
ok 300000 tokens
Test #16:
score: 0
Accepted
time: 221ms
memory: 252904kb
input:
300000 7687 5348 7170 7128 1126 3094 1811 2132 4535 2558 6168 62 1913 315 454 6832 2620 979 6268 2470 7745 4962 5836 455 2548 2645 1190 4820 1664 7069 1853 3559 1684 324 2964 2375 6535 2140 5793 6520 2089 2949 6810 6376 3938 1105 3321 2276 1764 7871 7238 4463 6621 6709 4794 1247 1193 3711 7945 25 75...
output:
467980791 680962696 898655348 87851601 574364215 617075952 975724718 232344677 97747094 798035755 544312119 750213987 398352588 468271115 911224185 789740750 889993565 757589351 219602000 508186836 143616463 496959998 957512294 48894767 747840016 237688107 834496842 452902067 436640761 68924558 4766...
result:
ok 300000 tokens
Test #17:
score: 0
Accepted
time: 226ms
memory: 253400kb
input:
300000 3651 4395 598 2124 7806 1885 6102 3232 1632 4425 2814 2949 2885 4010 719 5821 945 382 3259 3899 1193 2658 3681 176 6978 3339 5065 458 7910 7330 7480 2560 1144 4193 3047 5955 690 5384 6928 5609 238 904 6819 6617 2297 2464 1956 4427 3070 7665 57 5624 1382 7277 1510 931 5413 6319 4135 5153 1245 ...
output:
185080421 622515437 953285449 259657392 382766568 389748070 912098350 791812015 122470478 542646121 189378193 481103802 38378800 282397881 456885301 463133196 542482622 956189657 306447176 892824103 231973605 607936904 612962412 787715604 946988413 397452805 443819486 441909715 443478773 675662739 2...
result:
ok 300000 tokens
Test #18:
score: 0
Accepted
time: 196ms
memory: 253176kb
input:
300000 5511 1592 3091 222 3042 2846 4996 1848 2759 719 339 41 7833 6657 6578 4870 5836 3918 3287 2592 6888 254 323 257 3894 762 2781 147 6338 4197 2401 5526 309 111 499 475 68 1 1791 1498 1139 172 7367 5346 1326 1086 6056 3244 1539 870 2161 577 6899 4934 3222 2409 5094 4945 1252 389 7532 3877 4849 2...
output:
308162096 926831023 97466439 381502673 879141892 288558285 376988538 114780505 967786299 109837829 456357766 152648543 358087181 727740397 203822224 512742419 592251017 205442121 1 187347956 440265112 31975034 944117166 277099223 807372439 313788153 396485979 416038692 118014328 380422322 384451082 ...
result:
ok 300000 tokens
Test #19:
score: 0
Accepted
time: 214ms
memory: 253448kb
input:
300000 5511 2811 3091 225 3042 1281 4996 821 2759 267 339 292 7833 515 6578 5344 5836 1128 3287 398 6888 5910 323 266 3894 3721 2781 2271 6338 5322 6838 6497 309 243 499 486 68 11 1791 100 1139 514 7367 5113 1326 747 6056 1604 1539 782 2161 762 6899 4749 3222 2011 5094 3978 1252 623 7532 5477 4849 4...
output:
665054891 300867667 348283279 466053547 45744379 708735980 593404766 831832507 489279444 573407999 597639718 5766230 375599902 486548670 501927978 980593373 969955705 448325802 388400601 262385137 375376816 110122988 737706874 150359153 575621812 804184716 68665586 818047613 692689346 78602127 45512...
result:
ok 300000 tokens
Test #20:
score: 0
Accepted
time: 229ms
memory: 253784kb
input:
300000 5511 413 3091 2856 3042 1024 4996 3213 2759 105 339 327 7833 5988 6578 1636 5836 315 3287 1972 6888 1326 323 60 3894 816 2781 1712 6338 4382 2852 7641 309 57 499 167 68 23 1791 1375 1139 348 7367 6505 1326 435 6056 4617 1539 1133 2161 910 6899 1763 3222 1481 5094 2477 1252 1156 7532 6557 4849...
output:
485659367 677896371 51153808 69443182 412971885 818481416 849977792 331829138 55724792 462907888 637926 406804012 381350405 51624478 359208029 272155650 163436382 342656855 200714626 498916202 182274510 677459983 991151110 396383019 392439555 63570810 520284517 966012692 88444228 86200285 555967449 ...
result:
ok 300000 tokens
Test #21:
score: 0
Accepted
time: 217ms
memory: 253516kb
input:
300000 5511 2520 3091 2007 3042 2527 4996 267 2759 1311 339 7 7833 5969 6578 5180 5836 4504 3287 824 6888 1800 323 188 3894 2703 2781 113 6338 5373 210 667 309 5 499 463 68 45 1791 1776 1139 217 7367 6534 1326 193 6056 4824 1539 64 2161 626 6899 2131 3222 2304 5094 908 1252 622 7532 571 4849 1266 15...
output:
476330360 341129155 87686760 780287663 27737410 601067754 621911465 112461167 976022023 494331271 75971592 561865913 585445560 580978232 272409206 301199669 509769247 189882720 370830663 729977839 290413155 663712832 115843838 947770059 572260971 688396109 806982866 335384041 666428123 733355123 403...
result:
ok 300000 tokens
Test #22:
score: 0
Accepted
time: 208ms
memory: 253648kb
input:
300000 5511 2723 3091 2210 3042 1678 4996 3350 2759 1717 339 59 7833 6785 6578 1468 5836 5509 3287 2451 6888 4895 323 38 3894 2668 2781 2757 6338 5735 139 3773 309 296 499 359 68 51 1791 681 1139 990 7367 745 1326 327 6056 4864 1539 1125 2161 808 6899 890 3222 1023 5094 818 1252 185 7532 1083 4849 1...
output:
122256708 329468041 972582618 696900189 185355879 798415905 911105222 943525716 635145786 793642508 954014637 300072137 198622306 632297009 788106407 790602929 474908621 312319885 494386936 195749245 997359493 881353961 668060322 157183412 32778140 733123188 104542588 116382314 860154073 47295 78564...
result:
ok 300000 tokens
Test #23:
score: 0
Accepted
time: 199ms
memory: 253336kb
input:
300000 7522 7956 7746 7848 7995 7694 7479 7992 7878 7976 7532 7658 7679 7755 7462 7709 7610 7495 7877 7995 7915 7608 7883 7677 7467 7658 7615 7815 7521 7676 7455 7891 7868 7896 7634 7704 7869 7590 7471 7573 7472 7678 7885 7539 7983 7974 7478 7479 7705 7827 7675 7615 7915 7597 7644 7511 7903 7966 750...
output:
350858640 985201186 270505812 117456150 344107653 461416294 951152728 812878714 422195931 502806704 124570242 713987345 272798186 110562310 722669359 200627964 808703774 749707180 560860878 63011161 961348423 407734207 629246603 741475119 234863886 992855605 920110738 57955523 124147954 685852042 92...
result:
ok 300000 tokens
Extra Test:
score: 0
Extra Test Passed