QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#670454#9476. 012 Griducup-team902#AC ✓88ms20392kbC++173.0kb2024-10-23 21:47:502024-10-23 21:47:51

Judging History

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

  • [2024-10-23 21:47:51]
  • 评测
  • 测评结果:AC
  • 用时:88ms
  • 内存:20392kb
  • [2024-10-23 21:47:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1<<19;
const int mod=998244353;
using arr=int[N+5];
int add(int x,int y){ return (x+=y)>=mod?x-mod:x; }
int sub(int x,int y){ return (x-=y)<0?x+mod:x; }
void red(int &x){ x+=x>>31&mod;}
int ksm(ll x,int tp,int s=1){
    for(;tp;x=x*x%mod,tp>>=1) if(tp&1) s=x*s%mod;
    return s;
}
int fac[N+5],ifac[N+5];
void prep(){
    fac[0]=1;
    for(int i=1;i<=N;i++) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[N]=ksm(fac[N],mod-2);
    for(int i=N;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
}
int C(int n,int m){ return n<0||m<0||n<m?0:1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod; }
namespace poly_base{
	int l,n,iv; arr g;
	void r_prep(int tl){
		int i;
		l=(int)log2(tl-1)+1; n=1<<l;
		g[0]=1; g[n]=ksm(31,1<<21-l);
		for(i=l;i;i--) g[1<<i-1]=1ll*g[1<<i]*g[1<<i]%mod;
		for(i=0;i<n;i++) g[i]=1ll*g[i&i-1]*g[i&-i]%mod;
	}
	void prep(int tl){ n=1<<(l=(int)log2(tl-1)+1); iv=mod-(mod-1)/n; }
	void DIT(arr T){
		int i,*t,*j,*k,v;
		for(i=n>>1;i;i>>=1)
			for(t=g,j=T;j!=T+n;j+=i<<1,++t)
				for(k=j;k!=j+i;++k)
					v=1ll**t*k[i]%mod,red(k[i]=*k-v),red(*k+=v-mod);
	}
	void DIF(arr T){
		int i,*t,*j,*k,v;
		for(i=1;i<n;i<<=1)
			for(t=g,j=T;j!=T+n;j+=i<<1,++t)
				for(k=j;k!=j+i;++k)
					red(v=*k+k[i]-mod),k[i]=1ll**t*(*k-k[i]+mod)%mod,*k=v;
		reverse(T+1,T+n);
		for(int i=0;i<n;i++) T[i]=1ll*T[i]*iv%mod;
	}
	void NTT(arr a){ DIT(a); }
	void INTT(arr a){ DIF(a); }
	void NTT(arr a,arr b){ memcpy(b,a,n*sizeof(int)); DIT(b); }
	void INTT(arr a,arr b){ memcpy(b,a,n*sizeof(int)); DIF(b); }
}
namespace poly{
	using namespace poly_base;
	arr pa,pb,pc,pd,pe,pf;
	#define szf sizeof(int)
	void cl(arr a){ memset(a,0,n*szf); }
	void Mult(int t,arr a,arr b,arr c){
		if(t==1){ *c=1ll**a**b%mod; return; }
		prep(t); NTT(a,c); NTT(b,pa);
		for(int i=0;i<n;i++) c[i]=1ll*c[i]*pa[i]%mod;
		INTT(c); cl(pa);
	}
}
int h,w;
int ans;
arr f,g,res;
int work(int a,int b){
    return ((1ll*C(a+b-2,a-1)*C(a+b-2,b-1)-1ll*C(a+b-2,a)*C(a+b-2,b))%mod+mod)%mod;
}
void calc(int h,int w){
    for(int i=1;i<h;i++)
        ans=(ans+1ll*(h-i-1)*work(w,i))%mod;
}
int main(){
    prep();
    poly_base::r_prep(N);
    scanf("%d %d",&h,&w);
    for(int i=0;i<h;i++)
        f[i]=1ll*ifac[i]*ifac[i]%mod;
    for(int i=0;i<w;i++)
        g[i]=1ll*ifac[i]*ifac[i]%mod;
    poly::Mult(h+w,f,g,res);
    for(int i=0;i<h+w;i++)
        ans=(ans+1ll*fac[i]%mod*fac[i]%mod*res[i])%mod;
    memset(f,0,sizeof f);
    memset(g,0,sizeof g);
    memset(res,0,sizeof res);
    for(int i=1;i<h;i++)
        f[i]=1ll*ifac[i+1]*ifac[i-1]%mod;
    for(int i=1;i<w;i++)
        g[i]=1ll*ifac[i+1]*ifac[i-1]%mod;
    poly::Mult(h+w,f,g,res);
    for(int i=0;i<h+w;i++)
        ans=(ans-1ll*fac[i]%mod*fac[i]%mod*res[i])%mod;
    red(ans);
    // for(int i=1;i<=h;i++)
    //     for(int j=1;j<=w;j++)
    //         ans=add(ans,work(i,j));
    ans=add(ans,ans);
    calc(h,w);
    calc(w,h);
    ans=sub(ans,work(h,w));
    ans=add(ans,2);
    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 20384kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

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

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

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

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

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

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

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

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

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

input:

3 3

output:

64

result:

ok "64"

Test #7:

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

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

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

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

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

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

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

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

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

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

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

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

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

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

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

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

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

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

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

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

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

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

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

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

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

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

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

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

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

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

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

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

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

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

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

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 44ms
memory: 20256kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 39ms
memory: 20304kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 22ms
memory: 20240kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

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

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 45ms
memory: 20208kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

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

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 39ms
memory: 20328kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 39ms
memory: 20256kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 44ms
memory: 20360kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

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

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

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

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

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

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

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

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 17ms
memory: 20308kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 22ms
memory: 20360kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

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

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed