QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#413730#7632. Balanced ArraysgzyAC ✓20ms19380kbC++14796b2024-05-17 23:07:032024-05-17 23:07:03

Judging History

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

  • [2024-05-17 23:07:03]
  • 评测
  • 测评结果:AC
  • 用时:20ms
  • 内存:19380kb
  • [2024-05-17 23:07:03]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 7, M = 998244353;
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int i, j, k=1, n, m, res;
int v[N], f[N];

int C(int x, int y) {
	return f[x] * v[y] % M * v[x-y] % M;
}

int F(int x, int y) {
	return (C(x+y, x) * C(x+y, x) % M - C(x+y, y-1) * C(x+y, y+1) % M + M) % M;
}

signed main() {
	v[0] = v[1] = f[0] = f[1] = 1;
	for(i=2; i<N; i++) {
		f[i] = f[i-1] * i % M;
		v[i] = (M - M / i) * v[M % i] % M;
	}
	for(i=2; i<N; i++) v[i] = v[i] * v[i-1] % M;
	cin >> n >> m;
	for(i=0; i<=min(n, m); i++,k*=-1) (res += k * C(n, i) % M * F(n, m-i) % M + M) %= M;//, cout << i << " " << C(n, i) << " " << k << " " << F(n, m-i) << "\n";
	cout << res;
	return 0;
}


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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 19380kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

500000 500000

output:

984531374

result:

ok 1 number(s): "984531374"

Test #3:

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

input:

500000 1

output:

219705876

result:

ok 1 number(s): "219705876"

Test #4:

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

input:

1 500000

output:

500001

result:

ok 1 number(s): "500001"

Test #5:

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

input:

500000 353535

output:

33730077

result:

ok 1 number(s): "33730077"

Test #6:

score: 0
Accepted
time: 18ms
memory: 19296kb

input:

353535 500000

output:

182445298

result:

ok 1 number(s): "182445298"

Test #7:

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

input:

499999 499999

output:

933220940

result:

ok 1 number(s): "933220940"

Test #8:

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

input:

499999 499998

output:

899786345

result:

ok 1 number(s): "899786345"

Test #9:

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

input:

377773 400009

output:

206748715

result:

ok 1 number(s): "206748715"

Test #10:

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

input:

499999 100001

output:

482775773

result:

ok 1 number(s): "482775773"

Test #11:

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

input:

444445 488884

output:

70939759

result:

ok 1 number(s): "70939759"

Test #12:

score: 0
Accepted
time: 20ms
memory: 19160kb

input:

488885 444449

output:

591315327

result:

ok 1 number(s): "591315327"

Test #13:

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

input:

500000 111

output:

313439156

result:

ok 1 number(s): "313439156"

Test #14:

score: 0
Accepted
time: 15ms
memory: 19296kb

input:

333333 444444

output:

403492103

result:

ok 1 number(s): "403492103"

Test #15:

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

input:

499994 343433

output:

334451699

result:

ok 1 number(s): "334451699"

Test #16:

score: 0
Accepted
time: 20ms
memory: 19172kb

input:

477774 411113

output:

63883341

result:

ok 1 number(s): "63883341"

Test #17:

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

input:

123456 432109

output:

238795570

result:

ok 1 number(s): "238795570"

Test #18:

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

input:

131331 467777

output:

834790039

result:

ok 1 number(s): "834790039"

Test #19:

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

input:

500000 2

output:

304727284

result:

ok 1 number(s): "304727284"

Test #20:

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

input:

1111 111

output:

98321603

result:

ok 1 number(s): "98321603"

Test #21:

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

input:

416084 493105

output:

916827025

result:

ok 1 number(s): "916827025"

Test #22:

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

input:

53888 138663

output:

57263952

result:

ok 1 number(s): "57263952"

Test #23:

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

input:

219161 382743

output:

304889787

result:

ok 1 number(s): "304889787"

Test #24:

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

input:

181392 318090

output:

12528742

result:

ok 1 number(s): "12528742"

Test #25:

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

input:

135930 422947

output:

554153000

result:

ok 1 number(s): "554153000"

Test #26:

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

input:

280507 210276

output:

812816587

result:

ok 1 number(s): "812816587"

Test #27:

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

input:

253119 420465

output:

124024302

result:

ok 1 number(s): "124024302"

Test #28:

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

input:

446636 97448

output:

150388382

result:

ok 1 number(s): "150388382"

Test #29:

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

input:

284890 126665

output:

786559507

result:

ok 1 number(s): "786559507"

Test #30:

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

input:

186708 28279

output:

607509026

result:

ok 1 number(s): "607509026"

Extra Test:

score: 0
Extra Test Passed