QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#73057 | #4812. Counting Sequence | FISHER_ | ML | 1178ms | 867568kb | C++14 | 1.2kb | 2023-01-21 18:44:55 | 2023-01-21 18:44:58 |
Judging History
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