QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380431 | #5532. Kangaroo | nhuang685# | 0 | 0ms | 3588kb | C++20 | 1.9kb | 2024-04-07 03:50:08 | 2024-07-04 03:33:32 |
answer
#include <bits/stdc++.h>
const int MOD = (int)1e9 + 7;
struct Mint {
int val;
Mint(int v = 0) : val((v % MOD + MOD) % MOD) {}
Mint &operator+=(Mint b) {
val += b.val;
if (val >= MOD) {
val -= MOD;
}
return *this;
}
Mint &operator-=(Mint b) {
val -= b.val;
if (val < 0) {
val += MOD;
}
return *this;
}
};
Mint operator+(Mint a, Mint b) { return a += b; }
Mint operator-(Mint a, Mint b) { return a -= b; }
Mint psum(int l, int r, int p, std::vector<std::array<Mint, 2>> &v) {
if (l > r) {
return 0;
}
return v[r][p] - v[l - 1][p];
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
#ifdef LOCAL
std::freopen("input.txt", "r", stdin);
std::freopen("output.txt", "w", stdout);
#endif
int n, cs, cf;
std::cin >> n >> cs >> cf;
// std::vector dp(n + 1, std::vector(n + 1, std::vector(n + 1, std::array<Mint, 2>{0, 0})));
std::vector cur(n + 1, std::array<Mint, 2>{0, 0});
std::vector pre = cur;
pre[cs][0] = pre[cs][1] = 1;
for (int i = 2; i <= n; ++i) {
int l = cs - i + 1;
int r = cs + i - 1;
for (int fi = std::max(1, l); fi < cs; ++fi) {
cur[fi][0] = psum(fi + 1, std::min(n, r - 1), 1, pre);
cur[fi][1] = psum(std::max(2, l + 1), fi, 0, pre);
}
for (int fi = cs + 1; fi <= std::min(n, r); ++fi) {
cur[fi][0] = psum(fi, std::min(n - 1, r - 1), 1, pre);
cur[fi][1] = psum(std::max(1, l + 1), fi - 1, 0, pre);
}
if (i < n) {
for (int j = 1; j <= n; ++j) {
cur[j][0] += cur[j - 1][0];
cur[j][1] += cur[j - 1][1];
}
}
pre = cur;
cur.assign(n + 1, std::array<Mint, 2>{0, 0});
}
std::cout << (pre[cf][0] + pre[cf][1]).val << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3588kb
input:
7 3 6
output:
124
result:
wrong answer 1st numbers differ - expected: '14', found: '124'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%