QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380417 | #5532. Kangaroo | nhuang685# | 0 | 0ms | 0kb | C++20 | 2.0kb | 2024-04-07 03:26:12 | 2024-07-04 03:33:31 |
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);
#else
std::freopen("kangaroo.in", "r", stdin);
std::freopen("kangaroo.out", "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})));
dp[1][1][1][0] = dp[1][1][1][1] = 1;
for (int i = 2; i <= n; ++i) {
for (int st = 1; st <= i; ++st) {
for (int fi = 1; fi < st; ++fi) {
dp[i][st][fi][0] = psum(fi, i - 1, 1, dp[i - 1][st - 1]);
dp[i][st][fi][1] = psum(1, fi - 1, 0, dp[i - 1][st - 1]);
}
for (int fi = st + 1; fi <= i; ++fi) {
dp[i][st][fi][0] = psum(fi, i - 1, 1 , dp[i - 1][st]);
dp[i][st][fi][1] = psum(1, fi - 1, 0, dp[i - 1][st]);
}
if (i < n) {
for (int fi = 1; fi <= i; ++fi) {
for (int p : {0, 1}) {
dp[i][st][fi][p] += dp[i][st][fi - 1][p];
}
}
}
}
}
std::cout << (dp[n][cs][cf][0] + dp[n][cs][cf][1]).val << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
7 3 6
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%