QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #95764 | #5826. 错排 | william555 | 50 | 157ms | 180888kb | C++14 | 1.4kb | 2023-04-11 20:45:23 | 2023-04-11 20:45:26 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,mod=998244353;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int qpow(int a,int b){
int c=1;
for(;b;b>>=1,a=mul(a,a))if(b&1)c=mul(c,a);
return c;
}
int fac[N],ifac[N];
int n,m;
int f[5005][5005],ans[5005][5005];
void dp(){
f[0][0]=f[1][1]=1;
for(int i=2;i<=5000;i++){
for(int j=0;j<=i;j++){
if(j)f[i][j]=add(f[i-1][j-1],mul(i-1,add(f[i-1][j-1],f[i-2][j-1])));
f[i][j]=add(f[i][j],mul(i-1,add(f[i-1][j],f[i-2][j])));
}
}
for(int i=0;i<=5000;i++){
for(int j=0;j<<1<=i;j++){
ans[i][j]=mul(f[i-j][j],fac[j]);
}
}
}
int solve(int n,int m){
if(m<<1>n)return 0;
int ans=0;
for(int i=0;i<=n-m-m;i++){
int val=1ll*fac[n-m]*fac[n-m-i]%mod*ifac[i]%mod*ifac[n-m-m-i]%mod;
if(i&1)ans=add(ans,mod-val);
else ans=add(ans,val);
}
return ans;
}
int main(){
fac[0]=1;
for(int i=1;i<=200000;i++)fac[i]=mul(fac[i-1],i);
ifac[200000]=qpow(fac[200000],mod-2);
for(int i=200000;i>=1;i--)ifac[i-1]=mul(ifac[i],i);
int T;scanf("%d",&T);
// while(T--)solve();
dp();
while(T--){
int n,m;scanf("%d%d",&n,&m);
if(n<=5000&&m<=5000)printf("%d\n",ans[n][m]);
else printf("%d\n",solve(n,m));
}
return 0;
}
詳細信息
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 85ms
memory: 179352kb
input:
0
output:
result:
ok 0 number(s): ""
Subtask #2:
score: 9
Accepted
Test #2:
score: 9
Accepted
time: 82ms
memory: 180400kb
input:
10 8 6 5 1 4 2 6 3 8 1 3 1 6 2 3 1 4 1 6 2
output:
0 44 4 36 14833 2 168 2 9 168
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 77ms
memory: 177976kb
input:
10 8 1 8 4 6 3 8 2 8 3 6 3 6 1 7 3 2 1 8 3
output:
14833 576 36 10860 4680 36 265 432 1 4680
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 85ms
memory: 177820kb
input:
10 7 5 3 1 8 3 7 3 8 1 4 1 5 2 6 3 7 1 7 3
output:
0 2 4680 432 14833 9 24 36 1854 432
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 98ms
memory: 178356kb
input:
10 7 2 8 4 6 1 5 1 8 2 6 3 4 2 8 3 3 1 8 1
output:
1280 576 265 44 10860 36 4 4680 2 14833
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 73ms
memory: 175444kb
input:
10 6 6 3 1 8 3 2 1 7 1 3 1 6 2 8 4 7 3 7 0
output:
0 2 4680 1 1854 2 168 576 432 1854
result:
ok 10 numbers
Subtask #3:
score: 0
Time Limit Exceeded
Test #7:
score: 0
Time Limit Exceeded
input:
200000 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 0 12 0 13 0 14 0 15 0 16 0 17 0 18 0 19 0 20 0 21 0 22 0 23 0 24 0 25 0 26 0 27 0 28 0 29 0 30 0 31 0 32 0 33 0 34 0 35 0 36 0 37 0 38 0 39 0 40 0 41 0 42 0 43 0 44 0 45 0 46 0 47 0 48 0 49 0 50 0 51 0 52 0 53 0 54 0 55 0 56 0 57 0 58 0 59 0 60 0 61...
output:
0 1 2 9 44 265 1854 14833 133496 1334961 14684570 176214841 294304226 127281753 910981941 600290115 222488424 11814221 224470198 496426549 442513998 751108780 305347938 340640042 530046225 804025262 745550660 910531421 451058030 554564312 221339670 95158970 145512950 954462889 464137465 737039093 31...
result:
Subtask #4:
score: 20
Accepted
Test #8:
score: 20
Accepted
time: 140ms
memory: 178560kb
input:
200000 4303 1473 1276 72 967 234 3619 984 1316 384 2679 50 4426 1744 3782 1179 4919 4 805 63 3933 158 1574 528 1277 435 3826 915 2739 68 2286 349 3017 527 3036 476 4280 1764 1504 686 4584 917 1379 145 4764 2178 1881 45 4808 1565 3663 165 4730 2209 2258 103 4181 1687 1636 770 4339 1173 2355 777 3201 ...
output:
855518783 202627962 284771116 596280162 111952425 28114068 922980998 483503998 478475869 42227903 210453242 82826277 349706660 478397018 588903665 672339856 911511930 783922264 224272260 199537336 659467844 383745708 953695418 668329703 880293299 649430530 916687905 550953325 295023552 141584429 871...
result:
ok 200000 numbers
Test #9:
score: 0
Accepted
time: 142ms
memory: 175896kb
input:
200000 4558 644 2015 866 4752 1612 4343 704 4455 1277 4761 1069 1173 434 2150 1002 3226 132 4556 1468 4362 2008 3194 936 4750 1712 4133 58 4670 2111 3787 1705 1006 458 4973 1489 2520 934 3971 1256 4130 522 1648 28 4843 1800 3535 1031 2363 345 2722 1187 4620 1677 3738 325 3783 447 2026 617 4992 1595 ...
output:
878092359 137664342 571257477 157127504 385052631 35779181 650061801 617898174 375209372 721222702 707783783 410748088 991469920 69775359 76681433 134815341 199607624 126498594 149881281 563970794 786560573 94902562 668383803 802669973 229778708 749799553 295203934 163664840 140841030 547218181 2572...
result:
ok 200000 numbers
Test #10:
score: 0
Accepted
time: 157ms
memory: 175448kb
input:
200000 4763 4669 4281 319 1441 342 1078 224 2092 1022 1666 78 2623 660 4797 1258 4878 1616 3255 931 619 85 3632 220 3163 1358 4177 1838 3072 746 938 59 4038 1283 3825 618 4889 1090 3988 1380 686 237 4488 139 3189 572 4790 263 2862 340 3325 261 2351 1141 3047 659 2562 445 4947 1894 2504 717 3399 1176...
output:
0 283193141 728175842 611328334 18202018 506844457 979367956 585351167 337548843 72363572 243634086 313739474 707317304 637199005 278105669 961177961 957750794 767835509 349772711 198594249 245831996 37104891 398916514 263271106 843118755 308147020 690301962 174120745 179202564 216399429 946430481 7...
result:
ok 200000 numbers
Test #11:
score: 0
Accepted
time: 145ms
memory: 178192kb
input:
200000 1079 17 495 169 2890 659 3047 174 3199 761 2190 375 1947 159 4965 614 4463 1910 3630 321 4253 574 3175 871 2697 1262 3957 455 3435 205 2640 4 2181 935 1712 162 1152 351 3230 288 3887 1633 1094 374 833 295 3987 1856 844 179 2218 178 4922 683 4637 1988 2952 384 1493 720 4479 239 3366 1065 3663 ...
output:
158255419 402786997 811229485 767930818 68320941 852585187 491766976 228169531 315305063 656254912 979729105 514370258 749323558 931029769 871820770 342080940 688359960 983900818 13404663 552784020 781611444 697598838 340229841 78829168 776783084 20633291 315417596 788999254 586658522 557773549 5532...
result:
ok 200000 numbers
Test #12:
score: 0
Accepted
time: 131ms
memory: 179212kb
input:
200000 2864 223 4155 1498 2880 894 3933 1830 4207 973 2290 684 3522 1032 3713 910 4110 1341 4991 1550 4116 695 2484 943 2630 243 4943 418 1912 812 4457 2146 4979 678 1731 834 2555 625 3686 310 299 45 396 170 2876 997 4163 1859 4463 985 1617 450 4895 2328 2672 1177 3513 262 3843 1901 3070 1484 4954 1...
output:
629916892 381928609 997446852 27448639 502566091 127425081 674803798 840491154 578725589 88000079 914879351 221195824 389963150 790633997 798572067 76424829 35810515 100952206 612109651 277816564 59895360 717456537 370024748 46166162 89317834 803273270 844790653 676215132 402126887 644239704 5667377...
result:
ok 200000 numbers
Subtask #5:
score: 20
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #13:
score: 20
Accepted
time: 77ms
memory: 176948kb
input:
10 94764 1149 111140 21372 59140 20928 73376 27175 59837 4344 160865 25705 44518 10326 145794 64106 147628 12887 103719 39458
output:
139176963 393241499 258873190 39229362 870875380 975228452 243360193 751148936 95574458 297629235
result:
ok 10 numbers
Test #14:
score: 0
Accepted
time: 77ms
memory: 180832kb
input:
10 158002 80444 9451 2903 173427 12416 137154 16538 166581 24311 127365 41216 190696 67064 103832 40293 108767 52320 109966 50541
output:
0 702735124 750025710 841222658 375040035 583566228 649803213 746573713 113561055 257165994
result:
ok 10 numbers
Test #15:
score: 0
Accepted
time: 91ms
memory: 180888kb
input:
10 116222 34542 164940 69028 129899 24339 178863 5716 55643 22577 198734 88929 133306 14275 81416 35799 63999 8310 161489 76991
output:
290743004 378341801 539453217 748305238 182916741 547729744 354427924 684683519 325465086 252320707
result:
ok 10 numbers
Test #16:
score: 0
Accepted
time: 96ms
memory: 176268kb
input:
10 195516 163316 189541 26309 135594 44847 135877 65724 130088 25449 43733 28 99690 16935 64787 30191 71441 7633 149688 65415
output:
0 913189292 577808221 197261625 42734325 96320751 700077354 534988269 607854165 915606441
result:
ok 10 numbers
Test #17:
score: 0
Accepted
time: 102ms
memory: 178104kb
input:
10 163009 107578 44973 3654 143223 16359 94260 46849 30253 4092 157914 12798 96468 10458 69392 15738 175738 45794 88177 40742
output:
0 3532506 560207666 853291572 71222878 859859971 982136558 976170384 963781875 378642896
result:
ok 10 numbers
Test #18:
score: 0
Accepted
time: 97ms
memory: 178188kb
input:
10 110588 39549 80716 17407 111961 32201 141172 69526 113156 9733 197619 33476 175704 25422 193136 84984 121758 34704 186415 47390
output:
365752740 457468561 833768060 154200192 143999958 497510358 149082994 737572231 779740562 243498597
result:
ok 10 numbers
Test #19:
score: 0
Accepted
time: 109ms
memory: 177396kb
input:
10 135555 22650 164492 12323 142156 56953 147138 39540 198672 13148 113977 32999 140219 50353 70617 28677 163824 34306 189792 79678
output:
607236911 240877911 474627738 535731583 760041723 433248274 681491153 764919295 435671865 90602437
result:
ok 10 numbers
Test #20:
score: 0
Accepted
time: 102ms
memory: 174588kb
input:
10 170490 75332 171298 50434 192270 14874 169646 26194 148215 47449 184554 54250 89981 14289 155225 40485 117440 37074 176617 25601
output:
674081939 124446215 364039988 511947341 952033804 203192142 723185949 644885639 266757734 667462943
result:
ok 10 numbers
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%