QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#229817#7632. Balanced Arraysucup-team022#AC ✓166ms54356kbC++171.2kb2023-10-28 16:58:432023-10-28 16:58:43

Judging History

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

  • [2023-10-28 16:58:43]
  • 评测
  • 测评结果:AC
  • 用时:166ms
  • 内存:54356kb
  • [2023-10-28 16:58:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n, m;
int Power(int x, int y) {
	int r = 1;
	while (y) {
		if (y & 1) r = 1ll * r * x % mod;
		x = 1ll * x * x % mod, y >>= 1;
	}
	return r;
}
int f[500005][5][5];
void upd(int &x, int y) { x = (x + y) % mod; }
int Get(int n, int m) {
	memset(f, 0, sizeof(f));
	for (int i = 0; i <= m; i++) {
		f[1][i][i] = 1;
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= m; j++) {
			for (int k = 0; k <= m; k++) {
				for (int l = max(j - k, 0); l <= m; l++) {
					upd(f[i + 1][l][k - max(j - l, 0)], f[i][j][k]);
				}
			}
		}
	}
	int ans = 0;
	for (int j = 0; j <= m; j++)
		for (int k = 0; k <= m; k++) upd(ans, f[n][j][k]);
	return ans;
}
int h[500005];
int main() {
	cin >> n >> m;
	if (m <= 2) return cout << Get(n, m) << endl, 0;
	h[1] = Get(n, 1);
	h[2] = Get(n, 2);
	for (int i = 3; i <= m; i++) {
		int v1 = (mod - 1ll * n * (n + 1) % mod + mod - 2ll * i * i % mod) % mod;
		int v2 = (1ll * i * i - i + mod) % mod;
		h[i] = (mod - (1ll * v1 * h[i - 1] + 1ll * v2 * h[i - 2]) % mod * Power(i, mod - 2) % mod *
		                  Power(i + 1, mod - 2) % mod) %
		       mod;
	}
	cout << h[m];
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 163ms
memory: 54312kb

input:

500000 500000

output:

984531374

result:

ok 1 number(s): "984531374"

Test #3:

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

input:

500000 1

output:

219705876

result:

ok 1 number(s): "219705876"

Test #4:

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

input:

1 500000

output:

500001

result:

ok 1 number(s): "500001"

Test #5:

score: 0
Accepted
time: 130ms
memory: 54192kb

input:

500000 353535

output:

33730077

result:

ok 1 number(s): "33730077"

Test #6:

score: 0
Accepted
time: 149ms
memory: 54188kb

input:

353535 500000

output:

182445298

result:

ok 1 number(s): "182445298"

Test #7:

score: 0
Accepted
time: 162ms
memory: 54304kb

input:

499999 499999

output:

933220940

result:

ok 1 number(s): "933220940"

Test #8:

score: 0
Accepted
time: 166ms
memory: 54184kb

input:

499999 499998

output:

899786345

result:

ok 1 number(s): "899786345"

Test #9:

score: 0
Accepted
time: 130ms
memory: 54356kb

input:

377773 400009

output:

206748715

result:

ok 1 number(s): "206748715"

Test #10:

score: 0
Accepted
time: 60ms
memory: 53180kb

input:

499999 100001

output:

482775773

result:

ok 1 number(s): "482775773"

Test #11:

score: 0
Accepted
time: 154ms
memory: 54228kb

input:

444445 488884

output:

70939759

result:

ok 1 number(s): "70939759"

Test #12:

score: 0
Accepted
time: 153ms
memory: 54184kb

input:

488885 444449

output:

591315327

result:

ok 1 number(s): "591315327"

Test #13:

score: 0
Accepted
time: 37ms
memory: 52824kb

input:

500000 111

output:

313439156

result:

ok 1 number(s): "313439156"

Test #14:

score: 0
Accepted
time: 136ms
memory: 54172kb

input:

333333 444444

output:

403492103

result:

ok 1 number(s): "403492103"

Test #15:

score: 0
Accepted
time: 126ms
memory: 53532kb

input:

499994 343433

output:

334451699

result:

ok 1 number(s): "334451699"

Test #16:

score: 0
Accepted
time: 145ms
memory: 54228kb

input:

477774 411113

output:

63883341

result:

ok 1 number(s): "63883341"

Test #17:

score: 0
Accepted
time: 119ms
memory: 54228kb

input:

123456 432109

output:

238795570

result:

ok 1 number(s): "238795570"

Test #18:

score: 0
Accepted
time: 129ms
memory: 54136kb

input:

131331 467777

output:

834790039

result:

ok 1 number(s): "834790039"

Test #19:

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

input:

500000 2

output:

304727284

result:

ok 1 number(s): "304727284"

Test #20:

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

input:

1111 111

output:

98321603

result:

ok 1 number(s): "98321603"

Test #21:

score: 0
Accepted
time: 153ms
memory: 54184kb

input:

416084 493105

output:

916827025

result:

ok 1 number(s): "916827025"

Test #22:

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

input:

53888 138663

output:

57263952

result:

ok 1 number(s): "57263952"

Test #23:

score: 0
Accepted
time: 116ms
memory: 54080kb

input:

219161 382743

output:

304889787

result:

ok 1 number(s): "304889787"

Test #24:

score: 0
Accepted
time: 96ms
memory: 54108kb

input:

181392 318090

output:

12528742

result:

ok 1 number(s): "12528742"

Test #25:

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

input:

135930 422947

output:

554153000

result:

ok 1 number(s): "554153000"

Test #26:

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

input:

280507 210276

output:

812816587

result:

ok 1 number(s): "812816587"

Test #27:

score: 0
Accepted
time: 123ms
memory: 54224kb

input:

253119 420465

output:

124024302

result:

ok 1 number(s): "124024302"

Test #28:

score: 0
Accepted
time: 61ms
memory: 54148kb

input:

446636 97448

output:

150388382

result:

ok 1 number(s): "150388382"

Test #29:

score: 0
Accepted
time: 57ms
memory: 54188kb

input:

284890 126665

output:

786559507

result:

ok 1 number(s): "786559507"

Test #30:

score: 0
Accepted
time: 28ms
memory: 53292kb

input:

186708 28279

output:

607509026

result:

ok 1 number(s): "607509026"

Extra Test:

score: 0
Extra Test Passed