QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#397968 | #5047. Permutation | marher | RE | 91ms | 3724kb | C++17 | 851b | 2024-04-24 20:44:44 | 2024-04-24 20:44:53 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+50,mod=998244353;
int T,n,a[N],c,cm[N];
int solve(int l,int r,int x,int y)
{
if(l>n||r<1)return 1;
if(x+y>r-l+1)return cm[r-l+1];
if(r-l+1<=c)return cm[x]*cm[y]%mod;
int mi=1e9,pos=0;
for(int i=l;i<=r;i++)if(a[i]<mi)mi=a[i],pos=i;
if(pos>l+x-1&&pos<r-y+1)return solve(l,pos-1,x,(pos-l>=c)?c:0)*solve(pos+1,r,(r-pos>=c)?c:0,y)%mod;
if(pos<l+x)
{
swap(a[pos],a[l]);
return solve(l+1,r,c+x-1,y)*x%mod;
}
swap(a[pos],a[r]);
return solve(l,r-1,x,y+c-1)*y%mod;
}
void sol()
{
cin>>n>>c;
cm[0]=1;
for(int i=1;i<=n;i++)cin>>a[i],cm[i]=cm[i-1]*i%mod;
cout<<solve(1,n,0,0)<<'\n';
}
main()
{
// freopen("in.txt","r",stdin);
cin>>T;
while(T--)sol();
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3644kb
input:
5 5 3 3 4 2 1 5 5 4 4 2 1 3 5 5 2 4 5 3 1 2 5 3 4 3 2 1 5 5 2 2 3 1 5 4
output:
6 1 4 6 4
result:
ok 5 number(s): "6 1 4 6 4"
Test #2:
score: 0
Accepted
time: 91ms
memory: 3724kb
input:
100000 5 4 1 3 2 5 4 5 3 5 1 4 2 3 5 2 1 4 5 3 2 5 4 5 2 4 3 1 5 4 2 5 4 1 3 5 4 1 2 3 5 4 5 4 4 3 2 5 1 5 3 1 5 4 3 2 5 3 3 2 5 4 1 5 4 4 3 1 5 2 5 4 4 3 5 2 1 5 2 3 2 1 4 5 5 3 2 4 5 1 3 5 3 2 1 4 3 5 5 3 2 1 5 4 3 5 2 2 1 3 4 5 5 4 2 3 1 4 5 5 2 1 2 4 5 3 5 3 2 4 1 5 3 5 3 2 4 3 5 1 5 3 4 1 3 5 2...
output:
24 6 6 24 1 24 24 6 18 1 24 4 6 6 6 4 1 12 1 6 6 24 18 2 18 4 6 6 18 6 4 1 6 18 1 6 24 18 6 1 12 18 6 4 2 24 12 4 24 4 4 24 6 1 1 1 1 6 1 4 1 18 1 18 4 4 6 24 6 4 6 1 12 1 4 4 6 24 18 6 2 6 1 12 6 24 1 4 6 1 1 6 1 1 24 12 18 1 4 18 1 4 24 6 4 24 6 24 1 1 6 1 18 24 1 4 1 1 2 6 1 6 4 18 1 24 6 6 4 24 ...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 17ms
memory: 3580kb
input:
10000 10 2 7 4 2 9 1 3 10 5 8 6 10 7 10 6 1 5 2 4 7 9 8 3 10 4 10 7 6 2 8 1 5 4 3 9 10 4 4 9 6 2 10 7 8 5 1 3 10 5 9 8 7 4 5 3 2 10 6 1 10 3 5 7 8 1 9 4 6 10 3 2 10 4 6 2 10 8 4 7 9 5 3 1 10 5 10 1 3 7 5 9 4 2 8 6 10 7 10 3 4 5 6 1 9 2 8 7 10 4 1 8 9 7 5 6 3 10 4 2 10 3 6 7 3 1 9 4 10 8 5 2 10 3 5 1...
output:
432 5040 2304 24 201600 720 5040 120 1 20160 720 120 1 360 120 120 2160 141120 192 1 480 1 108 24 1 432 25200 1 30240 35280 35280 720 1800 576 1296 120 35280 20160 432 432 8 201600 192 432 141120 201600 2304 720 2880 576 1 120 201600 576 360 241920 40320 24 1 1 1 35280 1 1 1 3600 720 108 720 1 1296 ...
result:
ok 10000 numbers
Test #4:
score: 0
Accepted
time: 17ms
memory: 3620kb
input:
10000 10 3 8 6 7 1 10 9 5 3 2 4 10 8 2 9 3 4 10 7 1 5 6 8 10 4 5 2 3 4 10 8 9 7 6 1 10 8 8 4 9 2 5 3 7 1 6 10 10 2 1 8 6 5 4 3 2 10 7 9 10 8 2 4 7 3 6 1 10 9 8 5 10 4 6 9 1 7 8 2 3 10 5 4 10 8 1 9 8 3 2 5 6 10 7 4 10 4 5 2 6 3 7 8 1 4 9 10 10 9 4 3 1 5 9 10 7 6 2 8 10 5 10 4 7 9 8 6 1 3 2 5 10 4 3 8...
output:
144 1 5040 1 192 1 2880 322560 24 1 600 2304 1 1 36 1152 1 1 48 1 120 360 141120 1 1800 322560 2304 282240 362880 362880 480 120 120 48 1 24 36 201600 2160 35280 24 40320 25200 1 1 1296 1296 120 480 20160 480 322560 360 25200 141120 1 720 1 1 120 1152 1440 1 1 1 720 720 576 282240 432 1 1 1 40320 32...
result:
ok 10000 numbers
Test #5:
score: 0
Accepted
time: 19ms
memory: 3640kb
input:
10000 10 3 4 2 7 5 6 10 3 9 1 8 10 9 10 6 8 9 7 5 3 2 1 4 10 4 2 10 1 3 9 7 6 8 4 5 10 5 7 1 8 4 10 9 6 3 2 5 10 8 10 5 8 6 9 3 4 1 2 7 10 6 1 4 9 3 8 7 10 2 6 5 10 5 2 10 5 1 8 6 9 4 3 7 10 2 7 4 5 6 10 9 1 8 2 3 10 9 1 10 3 8 4 6 7 2 5 9 10 6 2 10 8 7 6 1 5 9 4 3 10 8 6 4 9 10 7 5 2 3 8 1 10 5 9 1...
output:
360 1 2880 720 1 720 600 48 362880 1 322560 120 432 720 1 5040 30240 24 96 48 2160 720 4320 1 1 720 1152 720 20160 2880 72 2160 35280 96 24 20160 282240 201600 1296 360 576 480 362880 120 40320 1 72 144 720 20160 72 20160 1 241920 20160 72 120 120 15120 360 5040 2880 1 2160 288 1 40320 40320 480 480...
result:
ok 10000 numbers
Test #6:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
1000 50 19 39 46 34 41 7 19 13 2 28 26 40 1 35 42 11 32 50 25 8 45 24 29 22 18 16 6 36 48 31 27 10 12 38 37 17 49 30 33 43 4 23 3 47 15 9 5 21 14 44 20 50 9 39 16 45 12 25 22 24 15 50 41 21 26 6 18 30 20 44 2 13 10 5 37 34 27 36 47 40 17 8 4 48 42 31 38 23 1 32 28 43 19 29 9 33 35 46 14 7 49 11 3 50...
output:
567646151 904915777 822371487 736050414 600774364 361781505 143685687 220211819 987913491 299469816 837902046 783901458 805655665 1 593639731 1 861744461 1 966786798 504900914 283559646 148890368 772701919 614643632 290522794 1 753390358 641491052 816418869 652885152 1 837902046 295294925 379831433 ...
result:
ok 1000 numbers
Test #7:
score: 0
Accepted
time: 7ms
memory: 3704kb
input:
1000 50 3 33 2 10 47 39 26 5 1 9 8 42 27 44 30 36 16 18 12 13 35 43 46 4 22 11 19 6 45 7 32 28 3 34 41 31 50 15 21 38 48 17 29 25 37 14 49 20 24 23 40 50 35 40 8 13 43 24 9 27 35 10 25 12 18 30 39 11 16 22 14 21 36 31 46 42 6 26 7 28 19 34 45 33 47 23 2 5 41 20 32 50 48 4 49 44 37 1 38 15 17 29 3 50...
output:
203567069 572108669 340897625 1 538293216 304827285 540519311 732552014 1 324879016 484802068 511305727 370610850 805869924 1 729545036 73799117 993629707 1 738017996 421226657 515245629 190572217 139305703 1 521746461 606263421 749940761 943237576 1 364507838 676326058 641491052 1 741967906 1 72935...
result:
ok 1000 numbers
Test #8:
score: 0
Accepted
time: 7ms
memory: 3576kb
input:
1000 50 19 33 46 22 48 2 50 11 49 29 4 42 32 40 37 35 18 30 23 36 6 7 27 41 3 26 19 25 14 34 1 20 38 44 24 16 10 47 31 8 5 15 21 13 9 28 12 45 43 39 17 50 12 37 12 30 22 44 21 4 10 17 34 45 43 42 29 7 25 5 48 23 20 14 50 40 1 2 11 13 16 28 49 36 38 6 15 18 19 39 3 27 35 32 8 26 9 46 31 24 47 33 41 5...
output:
93147306 121414421 186574145 59230529 1 1 141779823 526366254 380063818 845671530 970497268 978717980 63011703 1 211771833 1 1 1 676358722 612789666 1 657112938 561656917 839427168 20867134 567646151 589124132 593494012 1 856187068 1 706365909 1 920532689 785969121 1 855830729 460982724 316140945 79...
result:
ok 1000 numbers
Test #9:
score: 0
Accepted
time: 7ms
memory: 3624kb
input:
1000 50 35 45 33 24 31 27 36 7 23 42 15 39 22 41 3 37 48 2 49 20 38 26 35 25 9 28 50 30 46 8 43 4 18 44 1 5 12 21 40 17 19 16 14 29 34 47 6 13 10 11 32 50 38 14 11 35 7 50 4 41 24 18 12 27 19 1 5 22 13 28 17 16 8 43 46 32 49 21 36 48 33 9 31 44 23 2 30 37 25 40 45 26 15 3 38 6 20 10 39 34 29 47 42 5...
output:
1 1 918872114 1 799236323 851682606 466205103 672673398 986109411 237676512 215547397 526381028 30282727 380063818 969653692 549781074 499177977 1 676326058 1 23510511 567646151 123436377 660279506 1 1 230736384 1 847479521 428060021 97907900 339471033 1 1 452699684 1 593639731 767250218 1 1 9024167...
result:
ok 1000 numbers
Test #10:
score: 0
Accepted
time: 5ms
memory: 3636kb
input:
1000 50 35 25 41 33 23 24 12 42 46 45 10 7 16 43 26 39 15 35 11 19 5 21 22 40 9 29 31 3 48 34 36 47 1 27 49 4 6 20 37 17 14 8 28 18 50 44 30 38 2 13 32 50 32 9 25 10 48 28 39 18 6 26 47 40 45 44 30 38 13 37 49 31 11 1 36 32 12 33 7 21 24 43 4 34 20 22 41 16 50 42 19 2 29 5 35 14 3 46 15 17 23 8 27 5...
output:
1 1 1 966786798 62574862 914551701 512681272 726296738 736050414 1 748894162 816418869 59230529 254940118 1 1 978717980 918872114 1 380026194 914551701 254940118 1 833898700 937525290 1 966786798 331196124 590178664 516495362 958314234 864016726 561656917 368233794 507510371 1 283559646 951359943 10...
result:
ok 1000 numbers
Test #11:
score: 0
Accepted
time: 58ms
memory: 3648kb
input:
1000 500 494 212 491 495 442 426 314 341 42 22 247 499 277 226 406 497 209 105 302 213 231 246 123 427 74 466 329 423 89 488 118 250 236 286 360 299 463 51 37 91 112 116 184 10 185 359 59 313 124 297 500 139 82 251 249 238 357 293 381 194 120 462 319 97 401 420 181 198 187 321 374 349 68 308 354 13 ...
output:
1 369819598 79440751 826163737 1 203923370 975564702 636233236 22885662 587959123 210504484 62654757 63173954 325826961 613256208 515280304 542268941 566438719 358739333 241420315 1 1 613344817 690090622 209788531 217004985 266176189 1 69092736 801068619 216892151 195641568 1 697748554 743770407 636...
result:
ok 1000 numbers
Test #12:
score: 0
Accepted
time: 62ms
memory: 3664kb
input:
1000 500 34 431 471 482 232 447 126 478 427 405 418 251 333 407 361 476 9 448 48 276 419 373 138 454 273 160 260 296 432 81 347 79 475 340 225 171 239 422 32 286 86 337 8 129 14 257 289 210 164 338 384 256 493 192 5 227 435 39 283 346 98 13 263 443 102 282 204 46 304 127 100 18 119 179 65 52 157 430...
output:
642107110 994913686 569325635 144114861 981797303 373632628 1 237586273 583461679 435954006 339676851 1 1 530491163 682550749 144845479 788210049 655548099 879284515 1 1 891361363 1 1 107793378 348412766 1 748837249 952360967 990814597 862669788 148631681 1 968433321 630405774 967333268 516507942 1 ...
result:
ok 1000 numbers
Test #13:
score: 0
Accepted
time: 58ms
memory: 3656kb
input:
1000 500 410 34 378 77 192 408 295 308 484 293 360 73 371 199 262 403 32 263 443 54 266 286 147 152 63 53 254 181 313 94 255 474 131 129 169 10 93 290 498 35 141 58 27 203 372 52 98 315 281 240 347 116 243 303 213 174 419 66 83 301 260 134 464 144 154 238 46 310 305 457 109 410 170 418 400 339 184 2...
output:
158137008 1 901063286 975507056 1 691751126 1 517876374 1 51401571 962058390 761081352 1 441852974 195964339 80956464 888804009 735850380 131009036 137123897 58529921 1 1 1 696027122 127831228 131009036 483551773 395905754 33901266 431858460 221326270 745951239 805669961 738842231 1 1 936241441 8572...
result:
ok 1000 numbers
Test #14:
score: 0
Accepted
time: 66ms
memory: 3688kb
input:
100 5000 1734 3833 3764 1513 214 4943 189 3853 847 1880 2818 4150 4053 2526 1548 3736 3332 2251 4867 1941 3738 2184 2203 4179 4370 3509 3041 4472 1700 2672 70 271 4489 4363 1242 1066 4672 3327 2437 3013 582 4058 1617 296 4081 3174 2004 3847 2856 521 728 3380 2443 2337 4814 1269 3067 1356 450 2044 27...
output:
479539860 425871512 62427483 270105456 105638884 899923270 686908453 1 1 67946905 790358616 1 175157062 342927479 1 565285796 466220125 97218602 250089907 410446930 219040705 1 202216070 134795355 601016622 524256923 438171434 194366854 448499227 566906878 462990841 1 1 148108274 984972809 1 5377379...
result:
ok 100 numbers
Test #15:
score: 0
Accepted
time: 69ms
memory: 3704kb
input:
100 5000 3200 2756 4969 2724 2257 55 682 3774 4488 1664 3504 2146 1293 1494 2321 4829 4912 195 129 2837 981 4058 2561 3898 4402 4687 583 2860 742 4851 1234 1399 94 4929 4754 4784 526 1245 2229 3419 418 2284 4665 3447 3542 2610 4530 2719 4017 3864 1646 4571 609 2743 1195 3429 3803 3657 1431 25 4527 4...
output:
214249578 566341904 727615688 557417352 196515777 1 794847484 1 893958812 1 235155322 489698323 801357509 1 268786735 276045989 982338656 1 1 237198495 362607205 14383965 1 292714629 1 1 1 41233155 370099150 584677323 95102145 868158089 80536996 398874664 806738256 1 424734813 403007112 486376619 80...
result:
ok 100 numbers
Test #16:
score: 0
Accepted
time: 66ms
memory: 3712kb
input:
100 5000 3696 4765 492 1938 4448 4955 4354 2653 3108 429 3573 1 4605 450 745 1331 2010 4805 4784 240 2217 3245 2511 4973 4505 349 676 1100 4666 2992 4565 4359 4364 1492 1821 1583 3301 616 453 404 3228 3033 4229 158 2 4643 4788 3062 1112 4588 4154 3178 252 2394 1776 1659 603 2830 2356 4684 3267 4715 ...
output:
358487115 46468809 818168279 253942066 446600289 932734478 1 849757973 152390032 250656142 261364043 1 590596235 731357994 463879901 23555375 105295172 784500307 1 1 487388538 509410058 369765289 311230044 1 370046396 1 961162350 361771548 1 64559608 1 547217330 912387290 577805767 894965714 7608513...
result:
ok 100 numbers
Test #17:
score: -100
Runtime Error
input:
10 50000 13973 28116 20115 14842 25914 33088 48016 44516 10294 38893 32404 15477 46433 30415 39110 38711 7693 16807 27840 37896 6780 26529 26328 13098 30893 9114 8471 24678 4625 3410 23767 13714 19215 14825 44581 24274 41026 46943 17495 46167 15674 41733 32715 17893 38230 15315 7143 31352 10580 1714...