QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #88120 | #4558. 组合数问题 | DaiRuiChen007 | 100 ✓ | 216ms | 3784kb | C++14 | 968b | 2023-03-15 10:59:24 | 2023-03-15 10:59:25 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1e9+7;
int N[64],M[64],P;
int dp[64][2][2][2][2];
bool vis[64][2][2][2][2];
inline int dfs(int dig,bool ok,bool kn,bool km,bool kc) {
if(!dig) return ok?1:0;
if(vis[dig][ok][kn][km][kc]) return dp[dig][ok][kn][km][kc];
int ret=0;
for(int n=0;n<=(kn?N[dig]:P-1);++n) {
for(int m=0;m<=(km?M[dig]:P-1);++m) {
if(kc&&m>n) continue;
ret=(ret+dfs(dig-1,ok||(n<m),kn&&(n==N[dig]),km&&(m==M[dig]),kc&&(n==m)))%MOD;
}
}
vis[dig][ok][kn][km][kc]=true;
return dp[dig][ok][kn][km][kc]=ret;
}
inline void solve() {
int n,m; scanf("%lld%lld",&n,&m);
memset(N,0,sizeof(N)),memset(M,0,sizeof(M));
N[0]=0; while(n) N[++N[0]]=n%P,n/=P;
M[0]=0; while(m) M[++M[0]]=m%P,m/=P;
memset(vis,false,sizeof(vis));
memset(dp,0,sizeof(dp));
printf("%lld\n",dfs(63,0,1,1,1));
}
signed main() {
int T; scanf("%lld%lld",&T,&P);
while(T--) solve();
return 0;
}
详细
Test #1:
score: 5
Accepted
time: 0ms
memory: 3620kb
input:
100 79 92 96 83 22 13 68 65 42 60 24 7 41 51 7 41 67 39 19 31 78 30 78 68 56 31 8 10 10 69 1 84 96 22 49 39 1 22 11 50 20 3 96 1 59 58 73 92 16 47 63 99 23 13 1 24 3 33 70 56 35 24 80 96 98 2 17 9 33 45 97 60 93 14 75 26 78 71 88 86 3 25 24 32 93 75 71 51 41 3 72 53 1 28 44 75 26 97 38 27 12 64 41 8...
output:
1001 100 0 0 0 0 0 0 0 0 0 0 0 0 0 453 0 0 0 0 0 0 0 133 0 273 0 0 0 0 0 1251 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 551 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 803 0 0 0 270 666 0 0 0 70 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 803 0 0 1128 0
result:
ok 100 numbers
Test #2:
score: 5
Accepted
time: 2ms
memory: 3608kb
input:
100 17 22 63 46 63 82 13 97 53 40 59 19 67 47 93 93 1 63 68 50 26 76 93 39 64 6 65 51 34 15 65 65 71 77 27 42 90 65 67 73 69 11 53 61 75 95 51 63 68 20 59 57 75 24 83 25 87 97 84 9 46 29 12 14 94 71 3 70 28 52 59 35 42 15 99 66 76 34 41 53 70 65 98 24 52 81 79 93 94 41 6 74 94 19 90 78 4 57 91 63 97...
output:
81 396 364 1620 318 45 402 5 798 317 1248 298 0 440 0 813 688 352 813 1140 0 771 1587 798 58 681 100 108 2010 0 78 0 24 615 501 198 0 816 168 543 813 100 1348 1900 42 1180 45 40 681 798 1650 63 1179 1407 1781 133 408 1360 988 168 0 0 0 140 45 378 786 456 364 665 1096 996 45 0 525 0 298 663 115 1348 ...
result:
ok 100 numbers
Test #3:
score: 5
Accepted
time: 2ms
memory: 3612kb
input:
100 5 95 31 64 36 73 94 20 42 19 38 2 94 91 77 88 91 80 96 27 23 35 44 38 14 83 61 39 89 48 3 37 59 32 96 92 84 58 34 91 39 91 3 100 89 14 65 70 55 19 66 99 99 35 51 77 79 63 3 18 18 82 4 8 96 44 41 62 91 4 67 41 10 72 88 6 41 15 68 56 18 2 35 4 91 48 50 44 32 67 54 12 15 59 90 27 90 87 52 82 29 29 ...
output:
1435 953 1500 76 60 0 2478 2355 1903 166 345 225 1925 415 54 390 282 2556 815 1664 107 2876 30 1374 60 2800 345 1707 72 60 159 10 510 1152 0 169 1486 7 42 475 0 0 600 486 1301 28 1020 169 1945 1182 210 96 0 1101 1725 573 415 2034 947 57 1360 237 465 415 124 1517 60 1360 238 870 18 1116 51 10 30 738 ...
result:
ok 100 numbers
Test #4:
score: 5
Accepted
time: 3ms
memory: 3484kb
input:
100 41 36 59 75 13 14 97 70 21 14 12 10 49 63 28 55 36 12 12 1 56 87 35 88 65 100 33 2 24 30 89 3 16 98 9 57 6 46 41 82 33 72 28 12 80 7 92 25 95 38 51 26 44 99 26 95 47 91 74 47 26 88 41 93 94 29 79 48 47 57 29 88 22 5 69 20 85 52 38 85 53 49 94 44 96 75 50 12 53 72 69 7 7 37 92 46 79 18 28 59 91 3...
output:
0 91 0 231 0 0 391 435 0 0 825 1226 1017 0 0 0 90 21 225 594 406 0 0 0 0 0 666 1310 1460 161 1079 1648 0 292 357 386 0 0 390 1016 324 154 805 0 784 0 0 225 0 589 0 1430 0 0 0 1024 1142 496 0 1200 0 0 161 0 419 273 42 597 0 715 0 0 784 0 204 0 729 339 0 0 1 190 784 765 899 0 1044 33 479 792 805 1796 ...
result:
ok 100 numbers
Test #5:
score: 5
Accepted
time: 190ms
memory: 3532kb
input:
100 97 157636907627596876 427969701510019508 765115712350589297 873695181691844954 358816848469439717 683456980345707163 486301159530889632 870530821296905113 14131120364349138 137093732723668166 435321803486410539 560170747045807980 159682575504261721 382613312034917406 838116297085227121 926544317...
output:
390895063 5336761 22389128 453707890 656541051 189290165 129358427 437593261 699229411 356765880 346889733 983186012 428204444 697555584 651286822 892463586 478426429 365260167 706067811 895149367 475738755 212635914 66457864 237377510 320134322 533435894 410358473 595760688 205610943 387527261 9966...
result:
ok 100 numbers
Test #6:
score: 5
Accepted
time: 90ms
memory: 3536kb
input:
100 59 910318578900278283 915753970949692470 27775779501134616 459151036927202336 323198602512464363 983868513304711262 528931460653976237 884838979761165037 306468348004810114 950076699981724570 352162404307580848 527275761281489184 56299679062110126 361056383987446134 272215898218507958 3637902778...
output:
848765382 713683772 814708475 376862157 678111007 841428264 293833982 809942159 568773368 342328130 817790876 544298976 430271499 571116788 621629065 584532991 747191880 965097650 718459142 213936247 18118778 903695269 830918855 270683077 69880557 331574191 416209200 217640616 323127816 397721571 27...
result:
ok 100 numbers
Test #7:
score: 5
Accepted
time: 72ms
memory: 3560kb
input:
100 53 552061561669226143 566501294999363243 207494124545383180 897418201113382067 164977933563230197 854787832361926622 147888708615623625 192641066230111021 834210226816578112 909251485848969421 751424771469364583 994903322139110398 753493928694338291 763826346245581599 24560183775857615 580115775...
output:
760096677 345959969 930092409 955930871 328634368 529014653 319082342 94125610 327305352 756421463 428872878 792683702 43472200 732450597 823144249 183407089 927469485 572064415 359210014 104980295 707440632 766207476 260715305 827863546 676168879 618951508 922669169 274848347 720977173 258912295 36...
result:
ok 100 numbers
Test #8:
score: 5
Accepted
time: 4ms
memory: 3784kb
input:
100 2 487223097991657872 750572884491257886 431199916453724251 587995737618937421 155042136555532111 433152426902097937 85467395773049824 483617026000230695 814204093461458742 608237944102736195 842805780055861934 736531786567975050 281036609431305304 288870851390346261 568102258140607352 6476794510...
output:
921856554 295349864 692822483 594663615 702202653 316213891 109033366 129456652 435261047 164085654 95532112 512942160 311984402 538020075 416877646 280718797 961685085 649002146 287646637 651273235 27040183 796409855 27232717 950674890 970703260 737409541 824248437 98895391 755284724 187927454 8406...
result:
ok 100 numbers
Test #9:
score: 5
Accepted
time: 1ms
memory: 3764kb
input:
100 2 819788194069964073 946300224327602676 312251494531013138 604207780911401514 591788420248071150 314818351531720259 389608373558065314 586322534785228222 514438937937650023 138133998747608494 158945541403595594 119753614673973562 695029927528308652 369582773679299102 954836780855944387 716152938...
output:
106381936 936193659 9777935 366776044 732764069 284326526 740196853 593008986 664426434 191478326 267768209 67263709 487374835 828709906 382988112 631584941 252369287 292735544 863350923 458355878 997951162 532094441 251696342 797220302 236703027 99575917 441771225 104566643 502368385 777905313 3174...
result:
ok 100 numbers
Test #10:
score: 5
Accepted
time: 3ms
memory: 3484kb
input:
100 2 509295295705797874 372612087921270267 953850607688899546 217993419723984756 796469301560682476 45917922409916623 613235210539827342 230808762334520114 658672738016705867 259333899378447145 29353191628628047 552249277555542821 597474333616128237 725346143541415416 596219956645873178 94237404701...
output:
265498746 354621054 222459568 388857472 33180849 174741132 800526698 576197674 29998824 376630587 599870939 347883292 36424254 610121303 159327842 821636945 464037446 851745451 129487963 387687690 41590835 922412471 440989659 159839432 8850486 659952560 732092015 105342792 87260489 151171411 4445768...
result:
ok 100 numbers
Test #11:
score: 5
Accepted
time: 2ms
memory: 3608kb
input:
100 71 365200641694239389 8 670185766808326800 5 674613725123328677 6 723533872414067351 5 770504702700228134 8 356142236376065714 9 238692813251749300 7 530370765250718460 5 210047215528342505 6 444169222704494261 9 453551105643590298 5 41575158374342272 5 735288454418427179 8 264436161941503686 6 ...
output:
55803599 292329523 611573018 749858511 71000382 52650018 398101244 888335875 777721863 560407531 451140685 102109047 306629400 139429037 837311133 53906066 520338371 577491017 873656888 933104086 429522272 581290352 830419534 281138789 936252141 5253395 665471941 823162329 948949584 872506990 839963...
result:
ok 100 numbers
Test #12:
score: 5
Accepted
time: 1ms
memory: 3756kb
input:
100 73 844990439012576297 5 810102950988617860 8 337123122972536077 8 651274096782889591 8 587968843737924812 7 400596476295513764 6 929855598034571885 9 921928089496323408 5 960682408768595343 8 783820731945597950 9 932155911353879031 6 885119229043478437 5 338419613637561494 8 222948108568445755 5...
output:
184447233 348552058 836387277 658396616 649589070 415316536 310290706 337567146 569554340 145868185 375404672 913899426 91376319 864618282 370098055 773966949 568470908 307073219 410311365 930808349 692705654 764723247 541822903 887529644 270747510 640317212 441709747 918504966 170160482 185399459 7...
result:
ok 100 numbers
Test #13:
score: 5
Accepted
time: 1ms
memory: 3600kb
input:
100 59 677260543346039116 7 209426506220656219 9 571459760128212601 7 538151752553282079 6 815437982312372046 6 147624219439353510 5 942690882296835453 7 988817269037682232 5 536327769383586061 9 933726488214592111 6 845615893639603547 8 406265602956658716 9 362146482197394289 9 700624553539011221 7...
output:
32983529 897630172 196336268 703569763 740515768 950673890 670236964 182024082 56239424 987265115 236110560 306372484 691637288 792710193 708692785 884122144 812608684 875572809 754290411 791941672 260846284 650085261 183226098 119706450 271316606 114074631 207555581 285583896 997168718 581587453 78...
result:
ok 100 numbers
Test #14:
score: 5
Accepted
time: 5ms
memory: 3580kb
input:
100 5 557784309565295889 369103983677872168 22748428317389015 522380157523941413 403314570563694382 945905651134046338 276281201316755656 356515836610572967 625917062407616998 416172718196795857 452476284235025119 575415565767103379 194898125664825504 636380748623140944 538547679094402342 2152399640...
output:
403579305 353217105 688308699 338351071 436164801 281033225 880878733 391766282 216144314 682393995 202578867 541865672 456626516 561738572 365125727 336745554 882019800 481022070 796323684 792798455 80253272 224345906 859634087 919504885 321202322 156164915 219310372 904353811 249665210 758860130 4...
result:
ok 100 numbers
Test #15:
score: 5
Accepted
time: 50ms
memory: 3548kb
input:
100 37 343880336842754057 90150650026004063 961407485818463498 977931031432024896 938307567250643365 582568616585492509 425345132217779679 316979824002355148 485372183369314558 318330334846327203 322061164098238476 947183539345569793 722399696762834008 947999136407713478 710554455345463796 926949939...
output:
217208105 239288517 299856371 704699690 760652504 756522641 275242946 998567342 529888083 905189111 505170328 673352597 460253195 983564792 953348707 432907925 949003615 602422251 648543009 805443858 695518178 395825606 471358200 919330317 154166188 447314624 713790287 165209441 996841895 732814569 ...
result:
ok 100 numbers
Test #16:
score: 5
Accepted
time: 20ms
memory: 3584kb
input:
100 23 68097969425025721 715756801227166175 198116886430358151 917547361115373846 94604476266674379 735249894353433672 305453626067220302 103086082964075976 482372029935002635 821410378592246876 738613207708958130 645398606088464318 710439634592757801 875778524886347037 995811798374699270 1981703798...
output:
665763241 860561705 256579636 414243318 150307737 454875344 324994219 408217927 892384794 829091963 147440074 513615651 648714106 770380773 319314804 610793749 739266110 486462564 915777937 374517825 784916749 407458140 545234256 644929953 291338196 128584805 176791089 788156208 138478407 653011292 ...
result:
ok 100 numbers
Test #17:
score: 5
Accepted
time: 95ms
memory: 3604kb
input:
100 59 191724470482004084 501422792177371994 71139966149614550 859175812865092719 758993806182085386 497365855677217291 987477950817381565 367660776678556404 273978153092730865 773820262186563717 873322611911251066 5905496431099694 316198784799611777 19860518909267697 335707459294885892 375911242750...
output:
841038801 973832744 821197990 76965798 149275353 128352327 735784944 913646462 925326807 583696981 416967906 895166016 87611335 135151835 453188452 894720085 644554012 922756266 226564836 984179657 918628950 265627461 618321085 406573772 757400597 104500648 281619912 127910038 317981866 336340056 78...
result:
ok 100 numbers
Test #18:
score: 5
Accepted
time: 7ms
memory: 3780kb
input:
100 7 330153754287495326 621582923072566847 985738100162249644 943216550059140913 413712312448933056 318932200301550667 165399983816802162 943483832609172062 558177614311422957 351906183961463055 923410987801536368 28750713635228503 671606124514786510 263679835797923843 68751480712219886 50382121826...
output:
338973473 715325276 827076401 544687777 800846510 805154165 411904334 797006433 353769077 791083423 969035041 728571449 966285026 153491239 637441577 940785521 900915395 75351254 213759695 224566056 913913499 397336760 763619916 533536944 204863643 608479778 868361815 699970781 159654461 433102329 3...
result:
ok 100 numbers
Test #19:
score: 5
Accepted
time: 15ms
memory: 3488kb
input:
100 17 400797342327643479 391526828624268025 946127538696754076 890844172028114215 383702904857644607 354818565277297945 901438432957694092 111720809984778091 517959169066555921 119424097374374461 171452502360020257 549732604916601781 137312772360967505 360566517482664059 318048736640849406 41862254...
output:
895425848 468071315 859931254 325202019 973777951 114331847 953606927 941688278 299662883 327097330 958263635 414594048 891511018 115329858 746660542 60032014 606732527 493865005 199545261 232042598 506260235 895342760 789755702 639524752 674738507 94735062 936578803 516120062 454317500 333966879 20...
result:
ok 100 numbers
Test #20:
score: 5
Accepted
time: 216ms
memory: 3552kb
input:
100 89 712601674968009431 726062823247853208 103321495693325312 42886475917625312 103366554138460150 757773023930941550 507617466913737384 690673805021356348 235670503935012156 148608768045107385 333005008014627464 646880253724684101 882498954900741017 30320349237228473 865434187166340143 5122793264...
output:
227709270 201750188 663139145 228788909 630969106 160385764 174916286 67369565 970032350 968985306 385300278 791546853 848685348 475391074 448202316 993567803 386577109 745351962 28013404 223467589 37767506 340214257 795984541 623930927 264384429 75287796 998638258 9904098 869336345 469032665 234960...
result:
ok 100 numbers
Extra Test:
score: 0
Extra Test Passed