QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#418970#7632. Balanced ArrayshbsAC ✓124ms19460kbC++20826b2024-05-23 16:43:472024-05-23 16:43:48

Judging History

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

  • [2024-05-23 16:43:48]
  • 评测
  • 测评结果:AC
  • 用时:124ms
  • 内存:19460kb
  • [2024-05-23 16:43:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000005
int n,m,ans;
const int mod=998244353;
int jc[N],njc[N];
int ksm(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=ans*x%mod;
		x=x*x%mod,y>>=1;
	}
	return ans;
}
int C(int x,int y){
	if(x<y||x<0||y<0) return 0;
	return jc[x]*njc[y]%mod*njc[x-y]%mod;
}
int W(int x,int y){
	return C(x+y-2,y-1);
}
int F(int x,int y){
	return (W(x+1,y+1)*W(x+1,y+1)%mod-W(x,y+2)*W(x+2,y)%mod+mod)%mod;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	jc[0]=njc[0]=1;
	for(int i=1;i<=max(n,m)*2;i++) jc[i]=jc[i-1]*i%mod,njc[i]=ksm(jc[i],mod-2);
	for(int i=0,o=1;i<=min(n,m);i++,o*=-1){
		ans+=o*C(n,i)*F(n,m-i)%mod,ans%=mod,ans=(ans+mod)%mod;
		//printf("%lld %lld\n",C(n,i),F(n,m-i)%mod);
	}
	printf("%lld\n",ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5876kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 124ms
memory: 19380kb

input:

500000 500000

output:

984531374

result:

ok 1 number(s): "984531374"

Test #3:

score: 0
Accepted
time: 113ms
memory: 19460kb

input:

500000 1

output:

219705876

result:

ok 1 number(s): "219705876"

Test #4:

score: 0
Accepted
time: 114ms
memory: 19348kb

input:

1 500000

output:

500001

result:

ok 1 number(s): "500001"

Test #5:

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

input:

500000 353535

output:

33730077

result:

ok 1 number(s): "33730077"

Test #6:

score: 0
Accepted
time: 121ms
memory: 19400kb

input:

353535 500000

output:

182445298

result:

ok 1 number(s): "182445298"

Test #7:

score: 0
Accepted
time: 112ms
memory: 19456kb

input:

499999 499999

output:

933220940

result:

ok 1 number(s): "933220940"

Test #8:

score: 0
Accepted
time: 124ms
memory: 19456kb

input:

499999 499998

output:

899786345

result:

ok 1 number(s): "899786345"

Test #9:

score: 0
Accepted
time: 95ms
memory: 19200kb

input:

377773 400009

output:

206748715

result:

ok 1 number(s): "206748715"

Test #10:

score: 0
Accepted
time: 108ms
memory: 19448kb

input:

499999 100001

output:

482775773

result:

ok 1 number(s): "482775773"

Test #11:

score: 0
Accepted
time: 121ms
memory: 19352kb

input:

444445 488884

output:

70939759

result:

ok 1 number(s): "70939759"

Test #12:

score: 0
Accepted
time: 120ms
memory: 19176kb

input:

488885 444449

output:

591315327

result:

ok 1 number(s): "591315327"

Test #13:

score: 0
Accepted
time: 109ms
memory: 19392kb

input:

500000 111

output:

313439156

result:

ok 1 number(s): "313439156"

Test #14:

score: 0
Accepted
time: 108ms
memory: 18592kb

input:

333333 444444

output:

403492103

result:

ok 1 number(s): "403492103"

Test #15:

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

input:

499994 343433

output:

334451699

result:

ok 1 number(s): "334451699"

Test #16:

score: 0
Accepted
time: 109ms
memory: 19116kb

input:

477774 411113

output:

63883341

result:

ok 1 number(s): "63883341"

Test #17:

score: 0
Accepted
time: 97ms
memory: 18472kb

input:

123456 432109

output:

238795570

result:

ok 1 number(s): "238795570"

Test #18:

score: 0
Accepted
time: 101ms
memory: 18880kb

input:

131331 467777

output:

834790039

result:

ok 1 number(s): "834790039"

Test #19:

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

input:

500000 2

output:

304727284

result:

ok 1 number(s): "304727284"

Test #20:

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

input:

1111 111

output:

98321603

result:

ok 1 number(s): "98321603"

Test #21:

score: 0
Accepted
time: 121ms
memory: 19276kb

input:

416084 493105

output:

916827025

result:

ok 1 number(s): "916827025"

Test #22:

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

input:

53888 138663

output:

57263952

result:

ok 1 number(s): "57263952"

Test #23:

score: 0
Accepted
time: 92ms
memory: 17908kb

input:

219161 382743

output:

304889787

result:

ok 1 number(s): "304889787"

Test #24:

score: 0
Accepted
time: 73ms
memory: 15368kb

input:

181392 318090

output:

12528742

result:

ok 1 number(s): "12528742"

Test #25:

score: 0
Accepted
time: 99ms
memory: 18728kb

input:

135930 422947

output:

554153000

result:

ok 1 number(s): "554153000"

Test #26:

score: 0
Accepted
time: 68ms
memory: 15212kb

input:

280507 210276

output:

812816587

result:

ok 1 number(s): "812816587"

Test #27:

score: 0
Accepted
time: 97ms
memory: 18836kb

input:

253119 420465

output:

124024302

result:

ok 1 number(s): "124024302"

Test #28:

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

input:

446636 97448

output:

150388382

result:

ok 1 number(s): "150388382"

Test #29:

score: 0
Accepted
time: 68ms
memory: 14480kb

input:

284890 126665

output:

786559507

result:

ok 1 number(s): "786559507"

Test #30:

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

input:

186708 28279

output:

607509026

result:

ok 1 number(s): "607509026"

Extra Test:

score: 0
Extra Test Passed