Submission #699115

#	Time	Username	Problem	Language	Result	Execution time	Memory
699115		mate	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	23 ms	16084 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 = 2000;
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 <= i; j++) {
            if(i + 1 == s || i + 1 == e) {
                dp[i + 1][j + 1] += dp[i][j];
                dp[i + 1][j] += dp[i][j];
                continue;
            }
            int 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] << " ";
//    vector<int> vec;
//    for(int i = 1; i <= n; i++) {
//        vec.pb(i);
//    }
//    int cnt = 0;
//    do {
//        bool isGood = true;
//        if(vec[0] != s || vec.back() != e) continue;
//        for(int i = 2; i < vec.size(); i++) {
//            if(vec[i - 2] < vec[i - 1] && vec[i - 1] < vec[i]) {
//                isGood = false;
//                break;
//            }
//            if(vec[i - 2] > vec[i - 1] && vec[i - 1] > vec[i]) {
//                isGood = false;
//                break;
//            }
//        }
//        if(isGood) cnt++;
//    }while(next_permutation(vec.begin(), vec.end()));
//    cout << cnt << " ";
}

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