QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#658311#9476. 012 Griducup-team1004#AC ✓289ms61804kbC++142.6kb2024-10-19 16:36:462024-10-19 16:36:47

Judging History

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

  • [2024-10-19 16:36:47]
  • 评测
  • 测评结果:AC
  • 用时:289ms
  • 内存:61804kb
  • [2024-10-19 16:36:46]
  • 提交

answer

#include<bits/stdc++.h>
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
const int N=2.1e6+10,mod=998244353,inv3=(mod+1)/3;
inline int Mod(int a){return a<mod?a:a-mod;}
int l;
typedef long long ll;
ll fastpow(ll a,int b)
{
	ll s=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1) s=s*a%mod;
	return s;
}
void dif(int *a)
{
	ll x,y,wn;
	for(int i=l>>1;i;i>>=1)
	{
		wn=fastpow(3,(mod-1)/i/2);
		for(int j=0;j<l;j+=(i<<1))
			for(int k=0,w=1;k<i;k++,w=w*wn%mod)
			{
				x=a[j+k],y=a[i+j+k];
				a[j+k]=Mod(x+y);
				a[i+j+k]=(x-y+mod)*w%mod;
			}
	}
}
void dit(int *a)
{
	ll x,y,wn;
	for(int i=1;i<l;i<<=1)
	{
		wn=fastpow(inv3,(mod-1)/i/2);
		for(int j=0;j<l;j+=(i<<1))
			for(int k=0,w=1;k<i;k++,w=w*wn%mod)
			{
				x=a[j+k],y=1ll*a[i+j+k]*w%mod;
				a[j+k]=Mod(x+y),a[i+j+k]=Mod(x-y+mod);
			}
	}
	x=fastpow(l,mod-2);
	for(int i=0;i<l;i++) a[i]=a[i]*x%mod;
}
void mul(ll *a,ll *b,int n,int m,ll *c)
{
	static int A[N],B[N];
	for(l=1;l<=n+m;l<<=1);
	for(int i=0;i<l;i++) A[i]=B[i]=0;
	for(int i=0;i<=n;i++) A[i]=a[i];
	for(int i=0;i<=m;i++) B[i]=b[i];
	dif(A),dif(B);
	for(int i=0;i<l;i++) A[i]=1ll*A[i]*B[i]%mod;
	dit(A);
	for(int i=0;i<=n+m;i++) c[i]=A[i];
	for(int i=n+m+1;i<l;i++) c[i]=0;
}
ll a[N],b[N],c[N],fac[N],ifac[N];
int n,m;
void init(int n)
{
	fac[0]=ifac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
	ifac[n]=fastpow(fac[n],mod-2);
	for(int i=n-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}
void pls(ll &a,ll b){a=(a+b)%mod;}
ll F(int a,int b){return a<0||b<0?0:ifac[a]*ifac[b]%mod*fac[a+b]%mod;}
ll sq(ll x){return x*x%mod;}
int main()
{
	ll ans=2;
	scanf("%d%d",&n,&m);
	init(n+m);
	for(int i=0;i<n;i++) a[i]=sq(ifac[i]);
	for(int i=0;i<m;i++) b[i]=sq(ifac[i]);
	mul(a,b,n-1,m-1,c);
	for(int i=0;i<n+m-1;i++)
		pls(ans,c[i]*sq(fac[i]));
	a[0]=b[0]=0;
	for(int i=1;i<n;i++) a[i]=ifac[i-1]*ifac[i+1]%mod;
	for(int i=1;i<m;i++) b[i]=ifac[i-1]*ifac[i+1]%mod;
	mul(a,b,n-1,m-1,c);
	for(int i=2;i<n+m-1;i++)
		pls(ans,(mod-c[i])*sq(fac[i]));
	clr(a),clr(b);
	for(int i=0;i<n-1;i++) a[i]=sq(ifac[i]);
	for(int i=0;i<m-1;i++) b[i]=sq(ifac[i]);
	mul(a,b,n-1,m-1,c);
	for(int i=0;i<n+m-1;i++)
		pls(ans,c[i]*sq(fac[i]));
	a[0]=b[0]=0;
	for(int i=1;i<n-1;i++) a[i]=ifac[i-1]*ifac[i+1]%mod;
	for(int i=1;i<m-1;i++) b[i]=ifac[i-1]*ifac[i+1]%mod;
	mul(a,b,n-1,m-1,c);
	for(int i=2;i<n+m-1;i++)
		pls(ans,(mod-c[i])*sq(fac[i]));
	clr(a),clr(b);
	for(int i=1;i<n;i++)
	{
		pls(ans,(n-i)*sq(F(i-1,m-1)));
		pls(ans,(mod-(n-i))*F(i-2,m)%mod*F(i,m-2));
	}
	for(int i=1;i<m;i++)
	{
		pls(ans,(m-i)*sq(F(i-1,n-1)));
		pls(ans,(mod-(m-i))*F(i-2,n)%mod*F(i,n-2));
	}
	printf("%lld\n",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2

output:

11

result:

ok "11"

Test #2:

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

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 289ms
memory: 61656kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

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

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

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

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

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

input:

3 3

output:

64

result:

ok "64"

Test #7:

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

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

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

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

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

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

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

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

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

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

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

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

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

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

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

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

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

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

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

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

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

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

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

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

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

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 16ms
memory: 46912kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

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

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 16ms
memory: 45028kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

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

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 285ms
memory: 61676kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 133ms
memory: 55460kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 138ms
memory: 48008kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 69ms
memory: 55288kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 280ms
memory: 61780kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 134ms
memory: 52436kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 143ms
memory: 55748kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 133ms
memory: 55824kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 148ms
memory: 47884kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 146ms
memory: 48584kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 285ms
memory: 61804kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

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

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 284ms
memory: 58260kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

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

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 59ms
memory: 45544kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 72ms
memory: 47764kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

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

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed