QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#212358#4588. Feeder Robot275307894aAC ✓64ms11888kbC++142.0kb2023-10-13 15:13:452023-10-13 15:13:46

Judging History

This is the latest submission verdict.

  • [2023-10-13 15:13:46]
  • Judged
  • Verdict: AC
  • Time: 64ms
  • Memory: 11888kb
  • [2023-10-13 15:13:45]
  • Submitted

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'