QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#667871#9476. 012 Griducup-team3555AC ✓127ms33712kbC++142.2kb2024-10-23 09:10:252024-10-23 09:10:26

Judging History

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

  • [2024-10-23 09:10:26]
  • 评测
  • 测评结果:AC
  • 用时:127ms
  • 内存:33712kb
  • [2024-10-23 09:10:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N=5e5+5,H=998244353;
int n,m,fac[N],ifac[N],ans=0;

int adc(int a,int b){return a+b>=H?a+b-H:a+b;}
int dec(int a,int b){return a<b?a-b+H:a-b;}
int mul(int a,int b){return 1ll*a*b%H;}
void add(int &a,int b){a=adc(a,b);}
void del(int &a,int b){a=dec(a,b);}

int qpow(int a,int b=H-2){
  int res=1;
  while(b){if(b&1) res=mul(res,a);a=mul(a,a),b>>=1;}
  return res;
}

namespace Poly{
  #define poly vector<int>
  int U[N<<2],P,w[N<<2];
  const int g=3,ig=qpow(g);
  
  void Init(int n){
  	for(int i=1;i<=n;i++) U[i]=(U[i>>1]>>1)|((i&1)?n>>1:0);
  }
  
  void Cro(poly &F,poly G){
  	for(int i=0;i<(int)F.size();i++) F[i]=mul(F[i],G[i]);
  }
  
  void NTT(poly &p,int len,int op){
  	for(int i=0;i<len;i++) if(i<U[i]) swap(p[i],p[U[i]]);
  	int u,tmp;w[0]=1;
  	for(int k=2,lst=1;k<=len;lst=k,k<<=1){
  	  u=qpow(op==1?g:ig,(H-1)/k);
	  for(int i=1;i<=lst;i++) w[i]=mul(w[i-1],u);
	  for(int i=0;i<len;i+=k)
	    for(int l=i;l<i+lst;l++)
	      tmp=mul(p[l+lst],w[l-i]),p[l+lst]=dec(p[l],tmp),add(p[l],tmp);
	}
	if(op==-1){
	  int I=qpow(len);
	  for(int i=0;i<len;i++) p[i]=mul(p[i],I);
	}
  }
  
  poly operator *(poly F,poly G){
  	int n=(int)F.size(),m=(int)G.size();
  	for(P=1;P<n+m;P<<=1);
  	Init(P),F.resize(P),G.resize(P);
  	
  	NTT(F,P,1),NTT(G,P,1),Cro(F,G),NTT(F,P,-1);
  	
  	F.resize(n+m-1);return F;
  }
}
using namespace Poly;

void init(int n){
  fac[0]=1;
  for(int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
  ifac[n]=qpow(fac[n]);
  for(int i=n;i>=1;i--) ifac[i-1]=mul(ifac[i],i);
}

int calc(int x,int y){
  return mul(mul(fac[x+y-1],fac[x+y-2]),mul(mul(ifac[x],ifac[y]),mul(ifac[x-1],ifac[y-1])));
}

int main(){
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>m;
  init(n+m);
  
  poly F(n+m-1),G(n+m-1);
  
  for(int i=1;i<=n-1;i++) F[i]=mul(ifac[i],ifac[i-1]);
  for(int i=1;i<=m-1;i++) G[i]=mul(ifac[i],ifac[i-1]);
  
  F=F*G;
  
  for(int i=2;i<=n+m-2;i++) add(ans,mul(mul(fac[i-1],fac[i-2]),F[i]));
  ans=adc(mul(ans,2),2);
  for(int j=1;j<=m;j++) add(ans,mul(calc(n,j),m-j+1));
  for(int i=1;i<n;i++) add(ans,mul(calc(i,m),n-i+1));
  
  cout<<ans;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9676kb

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 2ms
memory: 9668kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 117ms
memory: 31772kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 2ms
memory: 9912kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 2ms
memory: 9668kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

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

input:

3 3

output:

64

result:

ok "64"

Test #7:

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

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 2ms
memory: 9676kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

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

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

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

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 2ms
memory: 9684kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 1ms
memory: 7688kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

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

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

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

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

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

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

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

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

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

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

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

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

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

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 2ms
memory: 12260kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

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

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

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

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

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

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 117ms
memory: 33064kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 52ms
memory: 20772kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 48ms
memory: 20524kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 25ms
memory: 13672kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 117ms
memory: 33136kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 54ms
memory: 20736kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 49ms
memory: 21616kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 51ms
memory: 20784kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 51ms
memory: 20940kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 49ms
memory: 21684kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 111ms
memory: 31580kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 110ms
memory: 33504kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 127ms
memory: 33712kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

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

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 25ms
memory: 17684kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 24ms
memory: 13508kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

score: 0
Accepted
time: 2ms
memory: 9636kb

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed