| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 528333 |
2022-02-20T03:42:08 Z |
KoD |
Kangaroo (CEOI16_kangaroo) |
C++17 |
|
68 ms |
756 KB |
#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
using ll = long long;
constexpr int MOD = 1000000007;
struct Fp {
int x;
Fp(const int x = 0) : x(x) {}
Fp& operator+=(const Fp& t) {
if ((x += t.x) >= MOD) x -= MOD;
return *this;
}
Fp operator+(const Fp& t) const {
return Fp(*this) += t;
}
Fp operator*(const Fp& t) const {
return Fp((ll)x * t.x % MOD);
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, src, dst;
std::cin >> N >> src >> dst;
vector<array<array<Fp, 2>, 2>> dp(1);
dp[0][1][0] = 1;
for (int cell = 2; cell <= N; ++cell) {
const int n = dp.size();
vector<array<array<Fp, 2>, 2>> next(n + 1);
if (cell != dst and cell <= src) {
for (int i = 0; i < n; ++i) for (int j : {0, 1}) for (int k : {0, 1}) {
if (j == 1) next[i + 1][1][k] += dp[i][j][k];
if (j == 1) next[i][0][k] += dp[i][j][k];
}
}
if (cell != src and cell <= dst) {
for (int i = 0; i < n; ++i) for (int j : {0, 1}) for (int k : {0, 1}) {
if (k == 0) next[i + 1][j][0] += dp[i][j][k];
if (k == 0) next[i][j][1] += dp[i][j][k];
}
}
if (cell != src and cell != dst) {
for (int i = 0; i < n; ++i) for (int j : {0, 1}) for (int k : {0, 1}) {
next[i + 1][j][k] += dp[i][j][k] * i;
if (i > 0) next[i - 1][j][k] += dp[i][j][k] * i;
}
}
dp = std::move(next);
}
Fp ans = 0;
for (int j : {0, 1}) for (int k : {0, 1}) {
ans += dp[0][j][k];
}
std::cout << ans.x << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
312 KB |
Output is correct |
| 13 |
Correct |
1 ms |
308 KB |
Output is correct |
| 14 |
Correct |
2 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
2 ms |
332 KB |
Output is correct |
| 18 |
Correct |
2 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
0 ms |
204 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
312 KB |
Output is correct |
| 13 |
Correct |
1 ms |
308 KB |
Output is correct |
| 14 |
Correct |
2 ms |
332 KB |
Output is correct |
| 15 |
Correct |
1 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
2 ms |
332 KB |
Output is correct |
| 18 |
Correct |
2 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
7 ms |
332 KB |
Output is correct |
| 22 |
Correct |
8 ms |
332 KB |
Output is correct |
| 23 |
Correct |
9 ms |
332 KB |
Output is correct |
| 24 |
Correct |
64 ms |
376 KB |
Output is correct |
| 25 |
Correct |
61 ms |
376 KB |
Output is correct |
| 26 |
Correct |
68 ms |
756 KB |
Output is correct |
| 27 |
Correct |
55 ms |
416 KB |
Output is correct |
| 28 |
Correct |
32 ms |
304 KB |
Output is correct |
