QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#656225#9476. 012 Griducup-team5077#AC ✓128ms47940kbC++142.9kb2024-10-19 11:52:312024-10-19 11:52:32

Judging History

This is the latest submission verdict.

  • [2024-10-19 11:52:32]
  • Judged
  • Verdict: AC
  • Time: 128ms
  • Memory: 47940kb
  • [2024-10-19 11:52:31]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e5+5,mod=998244353;

void gmod(int &x){
	x%=mod;
}

int ksm(int a,int x){
	int tot=1;
	while(x){
		if(x & 1ll) tot=tot*a%mod;
		a=a*a%mod;
		x>>=1ll;
	}
	return tot;
}

int mul[N],inv[N];
void init(int lim){
	mul[0]=inv[0]=1;
	for(int i=1;i<=lim;i++) mul[i]=mul[i-1]*i%mod;
	inv[lim]=ksm(mul[lim],mod-2);
	for(int i=lim-1;i>=1;i--) inv[i]=inv[i+1]*(i+1)%mod;
	
}

int C(int m,int n){
	if(m<0 || n<0 || m<n) return 0;
	return mul[m]*inv[n]%mod*inv[m-n]%mod;
}

namespace NTT{
	int A[N],B[N],C[N];
	int rev[N],pre[N];
	int init(int n){
		int lim=0;
		while((1ll<<lim)<=n) lim++;
		for(int i=0;i<(1<<lim);i++)
			rev[i]=(rev[i>>1] >> 1) | ((i & 1)<<(lim-1));
		int omega=ksm(3,(mod-1)/(1<<lim));
		pre[0]=1;
		for(int i=1;i<=(1<<lim);i++)
			pre[i]=pre[i-1]*omega%mod;
		return lim;
	}
	void ntt(int *f,int n,int opt){
		for(int i=0;i<n;i++){
			if(i<rev[i]) swap(f[i],f[rev[i]]);
		}
		for(int l=1;l<n;l*=2){
			for(int i=0;i<n;i+=l*2){
				int u=n/l/2,nw=(opt==1)?0:n;
				for(int j=0;j<l;j++){
					int x=f[i+j],y=pre[nw]*f[i+j+l]%mod;
					gmod(f[i+j]=x+y),gmod(f[i+j+l]=x+mod-y);
					nw+=opt*u;
				}
			}
		}
		if(opt==-1){
			int t=ksm(n,mod-2);
			for(int i=0;i<n;i++) f[i]=f[i]*t%mod;
		}
	}
	void solve(int *s,int *f,int *g,int n,int m){
		int lim=init(n+m);
		for(int i=0;i<=n;i++) A[i]=f[i];
		for(int i=0;i<=m;i++) B[i]=g[i];
		for(int i=n+1;i<(1<<lim);i++) A[i]=0;
		for(int i=m+1;i<(1<<lim);i++) B[i]=0;
		ntt(A,1<<lim,1);
		ntt(B,1<<lim,1);
		for(int i=0;i<(1<<lim);i++) s[i]=A[i]*B[i]%mod;
		ntt(s,(1<<lim),-1);
	}
}

int n,m;
int F[N],G[N],H[N];
signed main(){
	init(N-5);
	cin>>n>>m;
	
	int s2=(C(n-1+m-1,n-1)*C(n-1+m-1,n-1)%mod+mod-C(n-2+m,n-2)*C(n+m-2,n)%mod)%mod;
//	cout<<s2<<endl;
	
	int s1=0;
	for(int i=1;i<n;i++){
		gmod(s1+=(C(n-i+m,n-i)*C(n-i-1+m-1,n-i-1)%mod+mod-C(n-i+m-1,n-i)*C(n-i-1+m,n-i-1)%mod)%mod);
	}
	swap(n,m);
	int s4=0;
	for(int i=1;i<n;i++){
		gmod(s4+=(C(n-i+m,n-i)*C(n-i-1+m-1,n-i-1)%mod+mod-C(n-i+m-1,n-i)*C(n-i-1+m,n-i-1)%mod)%mod);
	}
//	cout<<s1<<" "<<s4<<endl;
	
	int s5=0;
	for(int d=1;d<n;d++){
		int c=n-1-d;
		gmod(s5+=(C(d-1+m,m)*C(d-1+m,m)%mod+mod-C(d+m,m)*C(d-2+m,m)%mod)%mod*c%mod);
	}
	
	swap(n,m);
	int s7=0;
	for(int d=1;d<n;d++){
		int c=n-1-d;
		gmod(s7+=(C(d-1+m,m)*C(d-1+m,m)%mod+mod-C(d+m,m)*C(d-2+m,m)%mod)%mod*c%mod);
	}
	swap(n,m);
	
	
	int s3=0;
	memset(F,0,sizeof(F));
	memset(G,0,sizeof(G));
	for(int i=1;i<n;i++) F[i]=inv[i]*inv[i-1]%mod;
	for(int i=1;i<m;i++) G[i]=inv[i]*inv[i-1]%mod;
	NTT::solve(H,F,G,n-1,m-1);
	for(int i=2;i<=n+m-2;i++)
		gmod(s3+=H[i]*(mul[i]%mod*mul[i-2]%mod+mod-mul[i-1]%mod*mul[i-1]%mod));
	int s9=s3;
	
	int ans=s2;
	gmod(ans+=(s1+s4)%mod*2%mod);
	gmod(ans+=(s5+s7)%mod);
	gmod(ans+=(s3+s9)%mod);
	cout<<(ans+2)%mod;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 31160kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 3ms
memory: 28092kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 128ms
memory: 47940kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 3ms
memory: 30960kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 10ms
memory: 29472kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

score: 0
Accepted
time: 7ms
memory: 30904kb

input:

3 3

output:

64

result:

ok "64"

Test #7:

score: 0
Accepted
time: 3ms
memory: 31204kb

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 5ms
memory: 27732kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

score: 0
Accepted
time: 6ms
memory: 30496kb

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

score: 0
Accepted
time: 0ms
memory: 31224kb

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 6ms
memory: 27696kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 5ms
memory: 31380kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

score: 0
Accepted
time: 9ms
memory: 27768kb

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 4ms
memory: 31696kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

score: 0
Accepted
time: 4ms
memory: 30964kb

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

score: 0
Accepted
time: 4ms
memory: 28008kb

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 8ms
memory: 32788kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 8ms
memory: 30960kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

score: 0
Accepted
time: 12ms
memory: 29860kb

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 4ms
memory: 28328kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

score: 0
Accepted
time: 12ms
memory: 29860kb

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 8ms
memory: 31328kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

score: 0
Accepted
time: 4ms
memory: 32744kb

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 122ms
memory: 45844kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 38ms
memory: 41736kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 40ms
memory: 42696kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 29ms
memory: 38220kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 126ms
memory: 45772kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 47ms
memory: 43232kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 42ms
memory: 42780kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 37ms
memory: 38360kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 33ms
memory: 43340kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 43ms
memory: 41936kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 125ms
memory: 47880kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 120ms
memory: 45824kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 119ms
memory: 45900kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

score: 0
Accepted
time: 7ms
memory: 33116kb

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 19ms
memory: 34512kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 20ms
memory: 37280kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

score: 0
Accepted
time: 7ms
memory: 30480kb

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed