QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#659212#9476. 012 Grid玩原神的都进队了 (Junlin Ye, Ruichen Dai, Chenghan Li)#AC ✓66ms24292kbC++202.7kb2024-10-19 19:16:172024-10-19 19:16:18

Judging History

This is the latest submission verdict.

  • [2024-10-19 19:16:18]
  • Judged
  • Verdict: AC
  • Time: 66ms
  • Memory: 24292kb
  • [2024-10-19 19:16:17]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
#define mod MOD
mt19937 rnd(time(0));
const int N=1<<19,MOD=998244353;
inline void add(int& x,ll y){ x=(x+y)%mod; }
int inv[N],fac[N],ifac[N];
namespace P {
const int G=3;
int rev[N],w[N<<1];
int ksm(int a,int b=MOD-2) {
	int ret=1;
	for(;b;a=1ll*a*a%MOD,b=b>>1) if(b&1) ret=1ll*ret*a%MOD;
	return ret;
}
void poly_init() {
	inv[1]=1;
	for(int i=2;i<N;++i) inv[i]=1ll*(MOD-MOD/i)*inv[MOD%i]%MOD;
	fac[0]=ifac[0]=1;
	for(int i=1;i<N;++i) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*inv[i]%MOD;
	for(int k=1;k<=N;k<<=1) {
		int x=ksm(G,(MOD-1)/k); w[k]=1;
		for(int i=1;i<k;++i) w[i+k]=1ll*x*w[i+k-1]%MOD;
	}
}
int plen(int x) { int y=1; for(;y<x;y<<=1); return y;  }
void ntt(int *f,bool idft,int n) {
	for(int i=0;i<n;++i) {
		rev[i]=(rev[i>>1]>>1);
		if(i&1) rev[i]|=n>>1;
	}
	for(int i=0;i<n;++i) if(rev[i]<i) swap(f[i],f[rev[i]]);
	for(int k=2,x,y;k<=n;k<<=1) {
		for(int i=0;i<n;i+=k) {
			for(int j=i;j<i+k/2;++j) {
				x=f[j],y=1ll*f[j+k/2]*w[k+j-i]%MOD;
				f[j]=(x+y>=MOD)?x+y-MOD:x+y,f[j+k/2]=(x>=y)?x-y:x+MOD-y;
			}
		}
	}
	if(idft) {
		reverse(f+1,f+n);
		for(int i=0,x=ksm(n);i<n;++i) f[i]=1ll*f[i]*x%MOD;
	}
}
void poly_mul(const int *f,const int *g,int *h,int n,int m) {
	static int a[N],b[N];
	for(int i=0;i<n;++i) a[i]=f[i];
	for(int i=0;i<m;++i) b[i]=g[i];
	int len=plen(n+m-1);
	ntt(a,0,len),ntt(b,0,len);
	for(int i=0;i<len;++i) h[i]=1ll*a[i]*b[i]%MOD;
	ntt(h,1,len);
	memset(a,0,sizeof(int)*len);
	memset(b,0,sizeof(int)*len);
}
}
int n,m;
inline constexpr int sqr(int x){ return (ll)x*x%mod; }
inline int binom(int u,int d){
	if(u<0||d>u) return 0;
	return (ll)fac[u]*ifac[d]%mod*ifac[u-d]%mod;
}
inline int calc(int x,int y){
	return (sqr(binom(x+y-2,x-1))-(ll)binom(x+y-2,x)*binom(x+y-2,x-2)%mod+mod)%mod;
}
inline int calc2(int i,int j){
	return (ll)sqr(fac[i+j-2])%mod*(i+j-1)%mod*
	sqr(ifac[i-1])%mod*sqr(ifac[j-1])%mod*P::ksm(i*j)%mod;
}
int f[N],g[N];
signed main(){
	P::poly_init();
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_Una.out","w",stdout);
	int n,m;
	cin>>n>>m;
	int ans=2;
	for(int i=1;i<n||i<m;i++){
		f[i]=(ll)sqr(ifac[i-1])*inv[i]%mod;
	}
	P::poly_mul(f,f,g,n,m);
	for(int i=2;i<=n+m-2;i++){
		add(ans,(ll)sqr(fac[i-2])*(i-1)%mod*g[i]%mod*2%mod);
	}
	// for(int i=1;i<n;i++){
	// 	for(int j=1;j<m;j++){
	// 		assert(calc(i,j)==calc2(i,j));
	// 		add(ans,2*calc2(i,j));
	// 	}
	// }
	for(int i=1;i<n;i++){
		add(ans,(ll)calc(m,i)*(n-i+1)%mod);
	}
	for(int i=1;i<m;i++){
		add(ans,(ll)calc(n,i)*(m-i+1)%mod);
	}
	add(ans,(ll)calc(n,m));
	cout<<ans<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 15ms
memory: 22116kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 11ms
memory: 22180kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 65ms
memory: 24288kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

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

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

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

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

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

input:

3 3

output:

64

result:

ok "64"

Test #7:

score: 0
Accepted
time: 14ms
memory: 22164kb

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 13ms
memory: 22232kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

score: 0
Accepted
time: 15ms
memory: 22236kb

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

score: 0
Accepted
time: 14ms
memory: 22064kb

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

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

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

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

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

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

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 15ms
memory: 22192kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

score: 0
Accepted
time: 11ms
memory: 22228kb

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

score: 0
Accepted
time: 15ms
memory: 22300kb

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 15ms
memory: 22228kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 15ms
memory: 22244kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

score: 0
Accepted
time: 15ms
memory: 22188kb

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 11ms
memory: 22132kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

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

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 15ms
memory: 22240kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

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

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 66ms
memory: 24180kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 30ms
memory: 23208kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 30ms
memory: 23144kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 18ms
memory: 22744kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 63ms
memory: 24216kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 35ms
memory: 23188kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 34ms
memory: 23144kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

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

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

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

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 34ms
memory: 23268kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 60ms
memory: 24176kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 65ms
memory: 24164kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 64ms
memory: 24292kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

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

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 18ms
memory: 22576kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 23ms
memory: 22644kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

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

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed