QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#659117#9476. 012 Griducup-team5318#AC ✓99ms32192kbC++142.7kb2024-10-19 18:43:532024-10-19 18:43:54

Judging History

你现在查看的是最新测评结果

  • [2024-10-19 18:43:54]
  • 评测
  • 测评结果:AC
  • 用时:99ms
  • 内存:32192kb
  • [2024-10-19 18:43:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second 
typedef vector<int> vi;
typedef pair<int,int> pi;

const int N=4e5+5, mod=998244353, i2=(mod+1)/2;
int qpow(int x,int y=mod-2){
	int res=1;
	while(y){
		if(y%2) res=res*x%mod;
		x=x*x%mod;
		y/=2;
	}
	return res;
}

namespace ntt{
	const int LG=19, S=1<<LG;
	int P[S];
	void init(){
		rep(i,0,LG-1){
			int stp=qpow(3,(mod-1)>>(i+1));
			P[1<<i]=1;
			rep(j,(1<<i)+1,(2<<i)-1){
				P[j]=P[j-1]*stp%mod;
			}
		}
	}
	void DIF(vi &a){
		per(i,LG-1,0){
			int len=1<<i;
			for(int j=0;j<S;j+=len*2){
				int idx=len;
				rep(k,j,j+len-1){
					int A=a[k], B=a[k+len];
					a[k]=(A+B)%mod, a[k+len]=(A-B+mod)*P[idx++]%mod;
				}
			}
		}
	}
	void DIT(vi &a){
		rep(i,0,LG-1){
			int len=1<<i;
			for(int j=0;j<S;j+=len*2){
				int idx=len;
				rep(k,j,j+len-1){
					int A=a[k], B=a[k+len]*P[idx++]%mod;
					a[k]=(A+B)%mod, a[k+len]=(A-B+mod)%mod;
				}
			}
		}
		int iv=qpow(i2, LG);
		reverse(a.begin()+1,a.end());
		for(int &x:a){
			(x*= iv )%=mod;
		}
	}
	vi mul(vi a,vi b){
		a.resize(S);
		b.resize(S);
		DIF(a); DIF(b);
		rep(i,0,S-1){
			(a[i]*= b[i] )%=mod;
		}
		DIT(a);
		return a;
	}
}
using ntt::mul;

int fac[N], ifac[N];
void init(){
	fac[0]=1;
	rep(i,1,N-1){
		fac[i]=fac[i-1]*i%mod;
	}
	ifac[N-1]=qpow(fac[N-1]);
	per(i,N-1,1){
		ifac[i-1]=ifac[i]*i%mod;
	}
}
int C(int m,int n){
	return n<0 || n>m? 0: fac[m]*ifac[n]%mod*ifac[m-n]%mod;
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#ifndef ONLINE_JUDGE
	assert(freopen(".in","r",stdin));
	assert(freopen(".out","w",stdout));
	#endif

	ntt::init();
	init();
	int n,m; cin>>n>>m;
	int ans=0;
	// rep(i,0,n-1){
	// 	rep(j,0,m-1){
	// 		(ans+= C(i+j,i)*C(i+j,i)-C(i+j,i-1)*C(i+j,j-1) )%=mod;
	// 	}
	// }
	vi x(n), y(m), z;
	rep(i,0,n-1){
		x[i]=ifac[i]*ifac[i]%mod;
	}
	rep(i,0,m-1){
		y[i]=ifac[i]*ifac[i]%mod;
	}
	z=mul(x,y);
	rep(i,0,n+m-1){
		(ans+= fac[i]*fac[i]%mod*z[i] )%=mod;
	}
	rep(i,0,n-1){
		x[i]=(i==0? 0: ifac[i-1]*ifac[i+1]%mod);
	}
	rep(i,0,m-1){
		y[i]=(i==0? 0: ifac[i-1]*ifac[i+1]%mod);
	}
	z=mul(x,y);
	rep(i,0,n+m-1){
		(ans-= fac[i]*fac[i]%mod*z[i] )%=mod;
	}

	(ans*= 2 )%=mod;
	rep(i,1,n-2){
		(ans+= ( C(m-2+i,i-1)*C(m-2+i,i-1)-C(m-2+i,i)*C(m-2+i,i-2) )%mod*(n-1-i) )%=mod;
	}
	rep(i,1,m-2){
		(ans+= ( C(n-2+i,i-1)*C(n-2+i,i-1)-C(n-2+i,i)*C(n-2+i,i-2) )%mod*(m-1-i) )%=mod;
	}
	ans+= 2;
	(ans-= C(n+m-2,n-1)*C(n+m-2,n-1)-C(n+m-2,n-2)*C(n+m-2,m-2) )%=mod;
	// (ans+= C())
	(ans+= mod )%=mod;
	cout<< ans <<'\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 84ms
memory: 25916kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 80ms
memory: 25916kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 92ms
memory: 32116kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 80ms
memory: 25716kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 88ms
memory: 25708kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

score: 0
Accepted
time: 82ms
memory: 25756kb

input:

3 3

output:

64

result:

ok "64"

Test #7:

score: 0
Accepted
time: 80ms
memory: 25916kb

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 79ms
memory: 25740kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

score: 0
Accepted
time: 83ms
memory: 25692kb

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

score: 0
Accepted
time: 85ms
memory: 25792kb

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 86ms
memory: 25912kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 83ms
memory: 25860kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

score: 0
Accepted
time: 82ms
memory: 25772kb

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 84ms
memory: 25972kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

score: 0
Accepted
time: 76ms
memory: 25840kb

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

score: 0
Accepted
time: 81ms
memory: 25876kb

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 76ms
memory: 25932kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 89ms
memory: 25876kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

score: 0
Accepted
time: 76ms
memory: 26120kb

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 86ms
memory: 26008kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

score: 0
Accepted
time: 77ms
memory: 25988kb

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 83ms
memory: 26124kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

score: 0
Accepted
time: 88ms
memory: 25896kb

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 90ms
memory: 31404kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 87ms
memory: 28360kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 87ms
memory: 27888kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 83ms
memory: 27352kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 92ms
memory: 31460kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 87ms
memory: 28980kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 89ms
memory: 28392kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 85ms
memory: 27920kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 83ms
memory: 27868kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 88ms
memory: 29216kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 83ms
memory: 32064kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 82ms
memory: 32152kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 99ms
memory: 32192kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

score: 0
Accepted
time: 88ms
memory: 25696kb

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 86ms
memory: 27316kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 86ms
memory: 27272kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

score: 0
Accepted
time: 83ms
memory: 25900kb

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed