Submission #699098

#	Time	Username	Problem	Language	Result	Execution time	Memory
699098		mate	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	1 ms	944 KiB

kangaroo

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back

using namespace std;

template <int MOD>
class Modular {
private:
    int val;
    static const int mod = MOD;
    Modular inverse (const Modular &A) {
        Modular u = 0, v = 1;
        int a = A.val;
        int b = mod;
        while(a != 0) {
            int t = b / a;
            b -= t * a; swap(b, a);
            u -= t * v; swap(u, v);
        }
        return (b == 1) ? u : 0;
    }
public:
    explicit operator int() const {
        return val;
    }
    Modular() { val = 0; }
    Modular(ll x) {
        val = x % mod;
        if(val < 0) val += mod;
    }
    friend bool operator==(const Modular &A, const Modular &B) { return A.val == B.val; }
    friend bool operator!=(const Modular &A, const Modular &B) { return A.val != B.val; }
    friend bool operator<(const Modular &A, const Modular &B) { return A.val < B.val; }
    friend bool operator>(const Modular &A, const Modular &B) { return A.val > B.val; }
    Modular &operator+=(const Modular &A) { val += A.val; val %= mod; return *this; }
    Modular &operator-=(const Modular &A) { val -= A.val; if(val < 0) val += mod; return *this; }
    Modular &operator*=(const Modular &A) { val = (int)((ll)val * A.val % mod); return *this; }
    Modular &operator/=(const Modular &A) { return *this *= inverse(A); }
    Modular operator-() const { return Modular(-val); }
    Modular &operator++() { return *this += 1; }
    Modular &operator--() { return *this -= 1; }
    friend Modular operator+(Modular A, const Modular &B) { return A += B; }
    friend Modular operator-(Modular A, const Modular &B) { return A -= B; }
    friend Modular operator*(Modular A, const Modular &B) { return A *= B; }
    friend Modular operator/(Modular A, const Modular &B) { return A /= B; }
    friend istream& operator>>(istream& stream, Modular &A) { ll x; stream >> x; A = Modular(x); return stream; }
    friend ostream& operator<<(ostream& stream, Modular &A) { return stream << A.val; }
};

const int N = 400;
const int mod = 1e9 + 7;
const int INF = 1e9 + 1;

using mint = Modular<mod>;

mint dp[N + 5][N + 5];

int main() {
    int n, s, e;
    cin >> n >> s >> e;
    dp[1][1] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == s || i == e) {
                dp[i + 1][j] += dp[i][j];
                continue;
            }
            int points;
            // Add in component
            points = j * 2;
            if(s < i) points--;
            if(e < i) points--;
            dp[i + 2][j] += dp[i][j] * points;
            // Add as component
            points = j + 1;
            if(s < i) points--;
            if(e < i) points--;
            dp[i + 1][j + 1] += dp[i][j] * points;
            // Marge components
            points = j - 1;
            dp[i + 1][j - 1] += dp[i][j] * points;
        }
    }
    cout << dp[n][1];
}

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