QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #359038 | #4812. Counting Sequence | james1BadCreeper | WA | 14ms | 19396kb | C++14 | 968b | 2024-03-20 11:19:49 | 2024-03-20 11:19:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;
const int N = 3e5 + 5, B = 800;
int n, c, ans;
int f[N][B], g[2][N * 2]; // sum = i, lst = j
int main(void) {
cin >> n >> c;
for (int i = 1; i <= min(n, B - 1); ++i) f[i][i] = 1;
for (int i = 2; i <= n; ++i) for (int j = 1; j <= min(i, B - 1); ++j) {
if (j > 1) f[i][j] = (f[i][j] + f[i - j][j - 1]) % P;
if (j + 1 < B) f[i][j] = (f[i][j] + 1ll * f[i - j][j + 1] * c) % P;
}
for (int i = 1; i <= min(n, B - 1); ++i) ans = (ans + f[n][i]) % P;
if (B <= n) ++ans;
g[1][0 + N] = 1;
for (int i = 2, now = 0; i * B <= n * 2; ++i, now ^= 1)
for (int j = -i * B + 1; j <= n - i * B; ++j) {
g[now][j + N] = (g[now ^ 1][j - (i - 1) + N] + 1ll * c * g[now ^ 1][j + (i - 1) + N]) % P;
if ((n - j) % i == 0) ans = (ans + g[now][j + N]);
}
cout << ans << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3612kb
input:
5 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
1 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 9952kb
input:
2022 39
output:
273239559
result:
ok 1 number(s): "273239559"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1 998244352
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
1 12345678
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3704kb
input:
20 998998
output:
643731701
result:
ok 1 number(s): "643731701"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
23 123
output:
947753998
result:
ok 1 number(s): "947753998"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
50 5555
output:
745339864
result:
ok 1 number(s): "745339864"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
60 6666
output:
690992218
result:
ok 1 number(s): "690992218"
Test #10:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
100 50
output:
169678588
result:
ok 1 number(s): "169678588"
Test #11:
score: 0
Accepted
time: 1ms
memory: 5112kb
input:
500 88888
output:
216149701
result:
ok 1 number(s): "216149701"
Test #12:
score: 0
Accepted
time: 4ms
memory: 6780kb
input:
1000 213456
output:
270989457
result:
ok 1 number(s): "270989457"
Test #13:
score: 0
Accepted
time: 4ms
memory: 9884kb
input:
2000 119988
output:
756425375
result:
ok 1 number(s): "756425375"
Test #14:
score: 0
Accepted
time: 14ms
memory: 12988kb
input:
3000 998244352
output:
71841227
result:
ok 1 number(s): "71841227"
Test #15:
score: 0
Accepted
time: 10ms
memory: 13036kb
input:
3000 555555555
output:
79880116
result:
ok 1 number(s): "79880116"
Test #16:
score: 0
Accepted
time: 11ms
memory: 17232kb
input:
4321 1234
output:
949603993
result:
ok 1 number(s): "949603993"
Test #17:
score: 0
Accepted
time: 11ms
memory: 19280kb
input:
5000 0
output:
5
result:
ok 1 number(s): "5"
Test #18:
score: -100
Wrong Answer
time: 12ms
memory: 19396kb
input:
5000 88888777
output:
-467169277
result:
wrong answer 1st numbers differ - expected: '833064960', found: '-467169277'