Submission #528333

#	Time	Username	Problem	Language	Result	Execution time	Memory
528333		KoD	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	68 ms	756 KiB

kangaroo

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 49 / 49