QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #313491 | #5826. 错排 | C1942huangjiaxu | 10 | 30ms | 7000kb | C++14 | 1.2kb | 2024-01-24 19:56:21 | 2024-01-24 19:56:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,P=998244353,bl=330;
int T,fac[N],inv[N],ifac[N],ans[N],pos[N],cq;
int A=1,B=1,v1=1,v2=1;
struct qry{
int a,b,id;
}q[N];
void init(){
fac[0]=inv[0]=fac[1]=inv[1]=ifac[0]=ifac[1]=1;
for(int i=2;i<N;++i)fac[i]=1ll*fac[i-1]*i%P,inv[i]=1ll*(P-P/i)*inv[P%i]%P;
for(int i=2;i<N;++i)ifac[i]=1ll*ifac[i-1]*inv[i]%P;
}
bool cmp(qry x,qry y){
if(pos[x.a]!=pos[y.a])return x.a<y.a;
return x.b<y.b;
}
int main(){
scanf("%d",&T);
init();
for(int i=1,n,m;i<=T;++i){
scanf("%d%d",&n,&m);
if(2*m>n)continue;
ans[i]=1ll*fac[n-m]*ifac[n-2*m]%P;
q[++cq]={n-2*m,m,i};
}
for(int i=1;i<N;++i)pos[i]=(i-1)/bl+1;
sort(q+1,q+cq+1,cmp);
for(int i=1;i<=cq;++i){
while(A<q[i].a){
v1=(1ll*A*v1+1ll*(A+B)*v2)%P;
swap(v1,v2);
++A;
}
while(A>q[i].a){
v2=(1ll*(P-v1)*(A+B-1)+v2)%P*inv[A-1]%P;
swap(v1,v2);
--A;
}
while(B<q[i].b){
v1=(v1+v2)%P;
v2=(1ll*A*v1+1ll*(B+1)*v2)%P;
++B;
}
while(B>q[i].b){
v2=(1ll*(P-v1)*A+v2)%P*inv[B]%P;
v1=(v1+P-v2)%P;
--B;
}
ans[q[i].id]=1ll*ans[q[i].id]*v2%P;
}
for(int i=1;i<=T;++i)printf("%d\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 1
Accepted
Test #1:
score: 1
Accepted
time: 2ms
memory: 5168kb
input:
0
output:
result:
ok 0 number(s): ""
Subtask #2:
score: 9
Accepted
Test #2:
score: 9
Accepted
time: 0ms
memory: 5508kb
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: 0ms
memory: 5440kb
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: 2ms
memory: 5468kb
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: 2ms
memory: 5436kb
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: 0ms
memory: 5368kb
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
Runtime Error
Test #7:
score: 0
Runtime Error
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: 0
Wrong Answer
Test #8:
score: 0
Wrong Answer
time: 30ms
memory: 7000kb
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:
wrong answer 917th numbers differ - expected: '620045262', found: '883835412'
Subtask #5:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #13:
score: 0
Runtime Error
input:
10 94764 1149 111140 21372 59140 20928 73376 27175 59837 4344 160865 25705 44518 10326 145794 64106 147628 12887 103719 39458
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%