QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#663875#9476. 012 GridrageOfThunder#AC ✓242ms73900kbC++233.5kb2024-10-21 18:04:502024-10-21 18:04:51

Judging History

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

  • [2024-10-21 18:04:51]
  • 评测
  • 测评结果:AC
  • 用时:242ms
  • 内存:73900kb
  • [2024-10-21 18:04:50]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
long long T,a,b,c,d[1000001],v[1000001],o,h[1000001],fa[1000001],q,w,e,an,cn,fac[1000001],inv[1000001],st[1000001],u[1000001],t[1000001][3],f[101][101];
char s[1000001];
struct p{long long q,w;}l[1000001],g[1000001];
long long tmp[1000001],tmp1[1000001],tmp2[1000001],id[1000001],lim=(1<<19),G=3,tmp3[1000001],lg;
long long pow_(long long qq,long long ww){long long ee=1;while(ww){if(ww&1) ee*=qq,ee%=mod;qq*=qq,qq%=mod,ww>>=1;}return ee%mod;}
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*f;}
void add(long long qq,long long ww){l[++o].q=ww,l[o].w=h[qq],h[qq]=o;}
long long gcd(long long qq,long long ww){return !ww?qq:gcd(ww,qq%ww);}
long long find(long long qq){return qq==fa[qq]?qq:fa[qq]=find(fa[qq]);}
void merge(long long qq,long long ww){long long f1=find(qq),f2=find(ww);if(f1==f2) return;fa[f1]=f2;}
long long C(long long qq,long long ww){if(qq<0||ww<0||qq<ww) return 0;return fac[qq]*inv[ww]%mod*inv[qq-ww]%mod;}
void ntt(long long *A,long long *B,long long fl)
{
	for(int i=0;i<lim;i++) B[i]=A[i];
	for(int i=0;i<lim;i++) if(i<id[i]) swap(B[i],B[id[i]]);
	for(int i=1;i<lim;i*=2)
	{
		long long un=pow_(G,(mod-1)/(i*2));
		if(fl==-1) un=pow_(un,mod-2);
		for(int j=0;j<lim;j+=i*2)
		{
			long long om=1;
			for(int k=0;k<i;k++)
			{
				long long x=B[j+k],y=B[i+j+k]*om%998244353;
				B[j+k]=(x+y)%998244353,B[i+j+k]=(x-y+998244353)%998244353;om=om*un%998244353;
			}
		}
	}
}
int main()
{
//	freopen("1.in","r",stdin);
	srand((unsigned)(time(0)^(*new int)));
	fac[0]=1;for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
	inv[1000000]=pow_(fac[1000000],mod-2);for(int i=999999;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
	scanf("%lld%lld",&a,&b);
	for(int i=a-1;i>=1;i--)
	{
		l[++cn]=p{0,i};
	}
	for(int i=0;i<b;i++) l[++cn]=p{i,0};
	cn=0;
	for(int i=1;i<=b;i++) g[++cn]=p{i,a};
	for(int i=a-1;i>=1;i--) g[++cn]=p{b,i};
	for(int i=1;i<=100;i++)
	{
		for(int j=1;j<=100;j++)
		{
//			0,1~i-1,j
//			1,0~i,j-1
			f[i][j]=(C(i+j-2,i-1)*C(i+j-2,i-1)-C(i+j-2,i-2)*C(i+j-2,i))%mod;
		}
	}
	lg=log2(lim);for(int i=0;i<lim;i++) id[i]=(id[i>>1]>>1)+((i&1)<<(lg-1));
	for(int i=0;i<=a-2;i++) tmp[i]=inv[i]*inv[i]%mod;
	for(int i=0;i<=b-1;i++) tmp1[i]=inv[i]*inv[i]%mod;
	ntt(tmp,tmp2,1);ntt(tmp1,tmp3,1);
	for(int i=0;i<lim;i++) tmp2[i]=tmp2[i]*tmp3[i]%mod;
	ntt(tmp2,tmp3,-1);long long tt=pow_(lim,mod-2);
	for(int i=0;i<lim;i++) tmp3[i]=tmp3[i]*tt%mod;
	for(int i=0;i<lim;i++) an=(an+tmp3[i]*fac[i]%mod*fac[i]%mod)%mod;
	memset(tmp,0,sizeof(tmp));
	memset(tmp1,0,sizeof(tmp1));
	for(int i=1;i<=a-2;i++) tmp[i]=inv[i-1]*inv[i+1]%mod;
	for(int i=1;i<=b-1;i++) tmp1[i]=inv[i-1]*inv[i+1]%mod;
	ntt(tmp,tmp2,1);ntt(tmp1,tmp3,1);
	for(int i=0;i<lim;i++) tmp2[i]=tmp2[i]*tmp3[i]%mod;
	ntt(tmp2,tmp3,-1);tt=pow_(lim,mod-2);
	for(int i=0;i<lim;i++) tmp3[i]=tmp3[i]*tt%mod;
	for(int i=0;i<lim;i++) an=(an-tmp3[i]*fac[i]%mod*fac[i]%mod)%mod;
//	for(int i=0;i<=a-2;i++)
//	{
//		for(int j=0;j<=b-1;j++)
//		{
//			an=(an+C(i+j,j)*C(i+j,i)-C(i+j,j-1)*C(i+j,i-1))%mod;
//		}
//	}
	an=an*2%mod;
	for(int i=1;i<=b;i++)
	{
		an=(an+(C(a+i-2,i-1)*C(a+i-2,i-1)-C(a+i-2,i-2)*C(a+i-2,i))%mod*(b-i+1))%mod;
	}
	for(int i=1;i<=a-2;i++)
	{
		an=(an+(C(b+i-2,i-1)*C(b+i-2,i-1)-C(b+i-2,i-2)*C(b+i-2,i))%mod*(a-1-i))%mod;
	}
	an=(an+2)%mod;
	printf("%lld",(an%mod+mod)%mod);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 206ms
memory: 58580kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 242ms
memory: 58692kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 212ms
memory: 73100kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 198ms
memory: 59192kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 205ms
memory: 60824kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

score: 0
Accepted
time: 204ms
memory: 61768kb

input:

3 3

output:

64

result:

ok "64"

Test #7:

score: 0
Accepted
time: 199ms
memory: 60264kb

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 206ms
memory: 58028kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

score: 0
Accepted
time: 210ms
memory: 59948kb

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

score: 0
Accepted
time: 203ms
memory: 60344kb

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 202ms
memory: 59884kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 208ms
memory: 61036kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

score: 0
Accepted
time: 216ms
memory: 60392kb

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 210ms
memory: 59840kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

score: 0
Accepted
time: 213ms
memory: 58564kb

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

score: 0
Accepted
time: 204ms
memory: 59376kb

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 217ms
memory: 58640kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 204ms
memory: 61736kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

score: 0
Accepted
time: 205ms
memory: 61016kb

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 205ms
memory: 58528kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

score: 0
Accepted
time: 211ms
memory: 59968kb

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 208ms
memory: 59332kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

score: 0
Accepted
time: 204ms
memory: 59284kb

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 216ms
memory: 69400kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 214ms
memory: 63916kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 208ms
memory: 63260kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 218ms
memory: 62276kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 221ms
memory: 71264kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 214ms
memory: 66656kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 193ms
memory: 67684kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 214ms
memory: 64980kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 207ms
memory: 63376kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 208ms
memory: 67728kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 222ms
memory: 73304kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 206ms
memory: 73900kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 215ms
memory: 73036kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

score: 0
Accepted
time: 207ms
memory: 59136kb

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 202ms
memory: 62232kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 207ms
memory: 63596kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

score: 0
Accepted
time: 199ms
memory: 59216kb

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed