QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#212358 | #4588. Feeder Robot | 275307894a | AC ✓ | 64ms | 11888kb | C++14 | 2.0kb | 2023-10-13 15:13:45 | 2023-10-13 15:13:46 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e5+5,M=1e6+5,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-6;const ll INF=1e18+7;mt19937 rnd(263082);
int n,m,A,k;ll frc[N],inv[N];
ll C(int x,int y){if(x<y||y<0) return 0;return frc[x]*inv[y]%mod*inv[x-y]%mod;}
ll calc(int x,int y,int w){if(x>y) return 0;return C(y+1,w+1)-C(x,w+1)+mod;}
struct ques{int x,y,w;}q[N*2];int qh;
const int inv2=(mod+1)/2;
void Solve(){
int i,j,h;scanf("%d%d%d",&n,&m,&A);
if(m==1){puts("1");return;}
inv[1]=1;for(i=2;i<=m;i++) inv[i]=(mod-inv[mod%i])*(mod/i)%mod;
for(frc[0]=inv[0]=i=1;i<=m;i++) frc[i]=frc[i-1]*i%mod,inv[i]=inv[i-1]*inv[i]%mod;
ll ans=0;
auto push=[](int l,int r,int x,int w){q[++qh]=(ques){x,r,w},q[++qh]=(ques){x,l-1,-w};};
for(i=1;i<=A;i++) {
/*for(j=A;j<=n;j++){
ans+=C((m+abs(i-A)-1)/2,j-i);
ans-=C(m/2-1,j-i);
}*/
push(A-i,n-i,(m+abs(i-A)-1)/2,1);
push(A-i,n-i,m/2-1,-1);
}
for(i=A;i<=n;i++){
/*for(j=1;j<=A;j++) {
ans+=C((m+abs(i-A)-1)/2,i-j);
ans-=C((m+1)/2-1,i-j);
}*/
push(i-A,i-1,(m+abs(i-A)-1)/2,1);
push(i-A,i-1,(m+1)/2-1,-1);
}
k=sqrt(max(n,m));
sort(q+1,q+qh+1,[](ques x,ques y){return x.x/k==y.x/k?x.y<y.y:x.x<y.x;});
int l=0,r=0;ll tot=1;
for(i=1;i<=qh;i++){
while(r<q[i].y) tot=(C(l,++r)+tot)%mod;
while(r>q[i].y) tot=(tot-C(l,r--))%mod;
while(l<q[i].x) tot=(tot*2-C(l++,r))%mod;
while(l>q[i].x) tot=(tot+C(--l,r))*inv2%mod;
ans+=tot*q[i].w;
}
printf("%lld\n",(ans%mod+mod)%mod);
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 8168kb
input:
4 3 2
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 1ms
memory: 6116kb
input:
3 5 2
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 1ms
memory: 6060kb
input:
3 6 2
output:
6
result:
ok single line: '6'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4068kb
input:
2 1 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 46ms
memory: 10720kb
input:
93844 52779 41066
output:
15948404
result:
ok single line: '15948404'
Test #6:
score: 0
Accepted
time: 45ms
memory: 11176kb
input:
92974 83483 82913
output:
636534890
result:
ok single line: '636534890'
Test #7:
score: 0
Accepted
time: 64ms
memory: 11436kb
input:
99638 137843 27168
output:
140741998
result:
ok single line: '140741998'
Test #8:
score: 0
Accepted
time: 57ms
memory: 11776kb
input:
94776 189552 75037
output:
10943210
result:
ok single line: '10943210'
Test #9:
score: 0
Accepted
time: 57ms
memory: 11856kb
input:
98122 196243 51898
output:
433580635
result:
ok single line: '433580635'
Test #10:
score: 0
Accepted
time: 37ms
memory: 11268kb
input:
94799 16084 53852
output:
541300035
result:
ok single line: '541300035'
Test #11:
score: 0
Accepted
time: 35ms
memory: 11108kb
input:
99255 16270 82986
output:
632634215
result:
ok single line: '632634215'
Test #12:
score: 0
Accepted
time: 30ms
memory: 11704kb
input:
90711 30608 30607
output:
307199727
result:
ok single line: '307199727'
Test #13:
score: 0
Accepted
time: 41ms
memory: 11604kb
input:
90871 32515 58901
output:
399181127
result:
ok single line: '399181127'
Test #14:
score: 0
Accepted
time: 47ms
memory: 11128kb
input:
93683 78004 78004
output:
831042401
result:
ok single line: '831042401'
Test #15:
score: 0
Accepted
time: 27ms
memory: 11880kb
input:
100000 200000 1
output:
589878665
result:
ok single line: '589878665'
Test #16:
score: 0
Accepted
time: 52ms
memory: 10888kb
input:
99571 80584 77484
output:
76979677
result:
ok single line: '76979677'
Test #17:
score: 0
Accepted
time: 46ms
memory: 11824kb
input:
98701 195293 85881
output:
919188077
result:
ok single line: '919188077'
Test #18:
score: 0
Accepted
time: 49ms
memory: 11704kb
input:
94737 189474 75712
output:
982200756
result:
ok single line: '982200756'
Test #19:
score: 0
Accepted
time: 50ms
memory: 11856kb
input:
98009 196017 45230
output:
524502520
result:
ok single line: '524502520'
Test #20:
score: 0
Accepted
time: 23ms
memory: 11444kb
input:
52049 35335 40627
output:
392902294
result:
ok single line: '392902294'
Test #21:
score: 0
Accepted
time: 0ms
memory: 6608kb
input:
7886 20819 5683
output:
880753789
result:
ok single line: '880753789'
Test #22:
score: 0
Accepted
time: 7ms
memory: 9116kb
input:
12935 110431 1855
output:
486933187
result:
ok single line: '486933187'
Test #23:
score: 0
Accepted
time: 5ms
memory: 9596kb
input:
6998 185600 5309
output:
875572529
result:
ok single line: '875572529'
Test #24:
score: 0
Accepted
time: 0ms
memory: 6248kb
input:
263 21165 110
output:
313229096
result:
ok single line: '313229096'
Test #25:
score: 0
Accepted
time: 1ms
memory: 6092kb
input:
219 53168 41
output:
76548690
result:
ok single line: '76548690'
Test #26:
score: 0
Accepted
time: 28ms
memory: 11464kb
input:
99999 54881 99999
output:
925367915
result:
ok single line: '925367915'
Test #27:
score: 0
Accepted
time: 2ms
memory: 8180kb
input:
203 147828 93
output:
200963393
result:
ok single line: '200963393'
Test #28:
score: 0
Accepted
time: 0ms
memory: 6504kb
input:
53 115859 8
output:
879480153
result:
ok single line: '879480153'
Test #29:
score: 0
Accepted
time: 1ms
memory: 6228kb
input:
11 72161 7
output:
977588182
result:
ok single line: '977588182'
Test #30:
score: 0
Accepted
time: 2ms
memory: 8680kb
input:
7 137778 2
output:
411775054
result:
ok single line: '411775054'
Test #31:
score: 0
Accepted
time: 0ms
memory: 6984kb
input:
2 118098 2
output:
1
result:
ok single line: '1'
Test #32:
score: 0
Accepted
time: 42ms
memory: 10664kb
input:
68183 89994 24513
output:
222225778
result:
ok single line: '222225778'
Test #33:
score: 0
Accepted
time: 28ms
memory: 10728kb
input:
61307 87410 55321
output:
786087147
result:
ok single line: '786087147'
Test #34:
score: 0
Accepted
time: 19ms
memory: 11068kb
input:
69764 19857 4202
output:
378716277
result:
ok single line: '378716277'
Test #35:
score: 0
Accepted
time: 61ms
memory: 11364kb
input:
96982 133359 63344
output:
538396098
result:
ok single line: '538396098'
Test #36:
score: 0
Accepted
time: 24ms
memory: 10076kb
input:
67065 34184 14110
output:
215549451
result:
ok single line: '215549451'
Test #37:
score: 0
Accepted
time: 26ms
memory: 11424kb
input:
99999 99999 1
output:
849329297
result:
ok single line: '849329297'
Test #38:
score: 0
Accepted
time: 17ms
memory: 8000kb
input:
35816 25787 26887
output:
157398762
result:
ok single line: '157398762'
Test #39:
score: 0
Accepted
time: 50ms
memory: 11888kb
input:
100000 200000 50000
output:
126901190
result:
ok single line: '126901190'
Test #40:
score: 0
Accepted
time: 40ms
memory: 11612kb
input:
95928 23066 68608
output:
719104244
result:
ok single line: '719104244'
Test #41:
score: 0
Accepted
time: 38ms
memory: 11080kb
input:
96028 13641 82388
output:
546657868
result:
ok single line: '546657868'
Test #42:
score: 0
Accepted
time: 35ms
memory: 11360kb
input:
95448 14579 80871
output:
854157868
result:
ok single line: '854157868'
Test #43:
score: 0
Accepted
time: 45ms
memory: 11752kb
input:
94236 50517 58764
output:
337054003
result:
ok single line: '337054003'