QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#73057#4812. Counting SequenceFISHER_ML 1178ms867568kbC++141.2kb2023-01-21 18:44:552023-01-21 18:44:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-21 18:44:58]
  • 评测
  • 测评结果:ML
  • 用时:1178ms
  • 内存:867568kb
  • [2023-01-21 18:44:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
inline int Mod(int x) { return x + ((x >> 31) & mod); }
inline int add(int x, int y) { return Mod(x + y - mod); }
inline int sub(int x, int y) { return Mod(x - y); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
const int maxn = 300000;
int f[maxn + 5][1100], g[2][2 * maxn + 5];
int n, c;
inline int sum(int l, int r) { return (l + r) * (r - l + 1) / 2; }
inline int& G(int i, int j) { return g[i][j + n]; }
int main() {
	scanf("%d%d", &n, &c);
	int B = sqrt(2 * n);
	for (int i = 1; i <= B; i++) f[i][i] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= i && (j <= B || sum(B, j) <= n); j++)
			f[i][j] = add(f[i][j], add(f[i - j][j + 1], mul(c, f[i - j][j - 1])));
	int ans = B < n;
	for (int i = 1; i <= B || sum(B, i) <= n; i++) ans = add(ans, f[n][i]);
	int now = 1, lst = 0;
	G(now, 0) = 1;
	for (int i = 2; i <= B; i++) {
		now ^= 1, lst ^= 1;
		memset(g[now], 0, sizeof(g[now]));
		for (int j = -sum(0, i - 1); j <= sum(0, i - 1); j++)
			G(now, j) = add(G(lst, j + i - 1), mul(c, G(lst, j - i + 1)));
		for(int j = B + 1; sum(j - i + 1, j) <= n; j++) ans = add(ans, G(now, n - j * i));
	}
	printf("%d", ans);
}

詳細信息

Test #1:

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

input:

5 3

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

1 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

2022 39

output:

273239559

result:

ok 1 number(s): "273239559"

Test #4:

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

input:

1 998244352

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

1 12345678

output:

1

result:

ok 1 number(s): "1"

Test #6:

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

input:

20 998998

output:

643731701

result:

ok 1 number(s): "643731701"

Test #7:

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

input:

23 123

output:

947753998

result:

ok 1 number(s): "947753998"

Test #8:

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

input:

50 5555

output:

745339864

result:

ok 1 number(s): "745339864"

Test #9:

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

input:

60 6666

output:

690992218

result:

ok 1 number(s): "690992218"

Test #10:

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

input:

100 50

output:

169678588

result:

ok 1 number(s): "169678588"

Test #11:

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

input:

500 88888

output:

216149701

result:

ok 1 number(s): "216149701"

Test #12:

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

input:

1000 213456

output:

270989457

result:

ok 1 number(s): "270989457"

Test #13:

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

input:

2000 119988

output:

756425375

result:

ok 1 number(s): "756425375"

Test #14:

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

input:

3000 998244352

output:

71841227

result:

ok 1 number(s): "71841227"

Test #15:

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

input:

3000 555555555

output:

79880116

result:

ok 1 number(s): "79880116"

Test #16:

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

input:

4321 1234

output:

949603993

result:

ok 1 number(s): "949603993"

Test #17:

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

input:

5000 0

output:

5

result:

ok 1 number(s): "5"

Test #18:

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

input:

5000 88888777

output:

833064960

result:

ok 1 number(s): "833064960"

Test #19:

score: 0
Accepted
time: 22ms
memory: 29744kb

input:

5000 35557777

output:

696388498

result:

ok 1 number(s): "696388498"

Test #20:

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

input:

10000 123456

output:

434296902

result:

ok 1 number(s): "434296902"

Test #21:

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

input:

20000 555555

output:

34806915

result:

ok 1 number(s): "34806915"

Test #22:

score: 0
Accepted
time: 90ms
memory: 137164kb

input:

30000 777888999

output:

58443551

result:

ok 1 number(s): "58443551"

Test #23:

score: 0
Accepted
time: 170ms
memory: 222992kb

input:

50000 2

output:

90102905

result:

ok 1 number(s): "90102905"

Test #24:

score: 0
Accepted
time: 265ms
memory: 309212kb

input:

70000 77998866

output:

202638568

result:

ok 1 number(s): "202638568"

Test #25:

score: 0
Accepted
time: 450ms
memory: 437892kb

input:

100000 998244352

output:

360520717

result:

ok 1 number(s): "360520717"

Test #26:

score: 0
Accepted
time: 454ms
memory: 437876kb

input:

100000 555555555

output:

613886009

result:

ok 1 number(s): "613886009"

Test #27:

score: 0
Accepted
time: 734ms
memory: 652948kb

input:

150000 233333

output:

381065878

result:

ok 1 number(s): "381065878"

Test #28:

score: 0
Accepted
time: 752ms
memory: 652940kb

input:

150000 20050117

output:

269891864

result:

ok 1 number(s): "269891864"

Test #29:

score: 0
Accepted
time: 1178ms
memory: 867568kb

input:

200000 114514

output:

262861613

result:

ok 1 number(s): "262861613"

Test #30:

score: 0
Accepted
time: 1146ms
memory: 867516kb

input:

200000 1919810

output:

77872388

result:

ok 1 number(s): "77872388"

Test #31:

score: -100
Memory Limit Exceeded

input:

300000 0

output:


result: