QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #90462 | #5826. 错排 | ytczy666 | 30 | 2960ms | 87372kb | C++14 | 2.5kb | 2023-03-23 10:17:37 | 2023-03-28 12:46:40 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::min;
using std::max;
using std::set;
using std::queue;
using std::sort;
using std::unique;
using std::vector;
using std::pair;
#define ll long long
#define db double
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define F(i,l,r) for(int i=(l);i<=(r);i++)
#define UF(i,l,r) for(int i=(l);i>=(r);i--)
#define mp std::make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls(x) x<<1
#define rs(x) x<<1|1
#define pb push_back
inline int rd(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
const int N=200010,mo=998244353;
inline int qk(int x){return x>=mo?x-mo:x;}
inline int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)ans=1ll*ans*a%mo;
a=1ll*a*a%mo;b>>=1;
}return ans;
}
int T,n,m,B,cb,Ce[3310][3310],fac[N],inv[N],len,rev[(1<<18)+5],f[(1<<18)+5],g[(1<<18)+5],Lim=200000,rec[70][N];
pii qry[N];
inline int C(int n,int m){
if(n<m||m<0)return 0;
return 1ll*fac[n]*inv[m]%mo*inv[n-m]%mo;
}
void ntt(int *a,int len,int op){
F(i,0,len-1)if(i<rev[i])std::swap(a[i],a[rev[i]]);
for(int i=2,o=1;i<=len;i<<=1,o<<=1){
int w=qpow(op==1?3:(mo+1)/3,(mo-1)/i);
for(int j=0;j<len;j+=i)for(int k=0,nw=1;k<o;k++,nw=1ll*nw*w%mo){
int A=a[j+k],B=a[j+k+o];
a[j+k]=qk(A+1ll*nw*B%mo);a[j+k+o]=qk(A-1ll*nw*B%mo+mo);
}
}
if(op==-1){
int iv=qpow(len,mo-2);
F(i,0,len-1)a[i]=1ll*a[i]*iv%mo;
}
}
int solve(int n,int m){
if(n<m)return 0;
int k=m/B,t=m-k*B,ans=0;
F(i,0,t)ans=qk(ans+1ll*Ce[t][i]*rec[k][n-i]%mo);
return ans;
}
int main(){
T=rd();Lim=3000;Ce[0][0]=1;
F(i,1,Lim){
Ce[i][0]=1;
F(j,1,i)Ce[i][j]=qk(Ce[i-1][j]+Ce[i-1][j-1]);
}
F(i,1,T)qry[i].fi=rd(),qry[i].se=rd(),Lim=max(Lim,qry[i].fi-qry[i].se);
fac[0]=inv[0]=1;
F(i,1,Lim)fac[i]=1ll*fac[i-1]*i%mo;
inv[Lim]=qpow(fac[Lim],mo-2);
UF(i,Lim-1,1)inv[i]=1ll*inv[i+1]*(i+1)%mo;
rec[0][0]=f[0]=1;rec[0][1]=f[1]=0;
F(i,2,Lim)f[i]=1ll*(i-1)*(f[i-1]+f[i-2])%mo,rec[0][i]=f[i];
B=3000;cb=Lim/B;
len=1;while(len<Lim+B+1)len<<=1;
F(i,1,len-1){
rev[i]=rev[i>>1]>>1;
if(i&1)rev[i]|=(len>>1);
}
F(i,1,cb){
F(j,0,B)g[j]=Ce[B][j];F(j,B+1,len-1)g[j]=0;
F(j,0,Lim)f[j]=rec[i-1][j];F(j,Lim+1,len-1)f[j]=0;
ntt(f,len,1);ntt(g,len,1);
F(j,0,len-1)rec[i][j]=1ll*f[j]*g[j]%mo;
ntt(rec[i],len,-1);
}
F(i,1,T){
n=qry[i].fi;m=qry[i].se;
cout<<1ll*fac[m]*C(n-m,m)%mo*solve(n-m,m)%mo<<"\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 6ms
memory: 50496kb
input:
0
output:
result:
ok 0 number(s): ""
Subtask #2:
score: 9
Accepted
Test #2:
score: 9
Accepted
time: 5ms
memory: 50416kb
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: 3ms
memory: 52548kb
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: 3ms
memory: 52588kb
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: 3ms
memory: 50492kb
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: 3ms
memory: 52552kb
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:
result:
Subtask #4:
score: 20
Accepted
Test #8:
score: 20
Accepted
time: 302ms
memory: 52204kb
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: 307ms
memory: 51364kb
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: 302ms
memory: 53752kb
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: 292ms
memory: 51904kb
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: 290ms
memory: 51380kb
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: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #13:
score: 20
Accepted
time: 2960ms
memory: 87372kb
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: -20
Time Limit Exceeded
input:
10 158002 80444 9451 2903 173427 12416 137154 16538 166581 24311 127365 41216 190696 67064 103832 40293 108767 52320 109966 50541
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%