oj.uz

Submission #322007

# Submission time Handle Problem Language Result Execution time Memory
322007 2020-11-13T17:04:26 Z EndRay Kangaroo (CEOI16_kangaroo) C++17
6 / 100
 22 ms 492 KB 
#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2000+1, mod = 1e9+7;

int n, i, j;

map<int, map<int, ll>> mp[N];

ll binpow(ll a, ll s){
    ll ans = 1;
    while(s){
        if(s&1)
            ans = ans*a%mod;
        a = a*a%mod;
        s >>= 1;
    }
    return ans;
}
ll inv(ll a){
    return binpow(a, mod-2);
}
ll fact[N], ifact[N];
ll C(int n, int k){
    return fact[n]*ifact[k]%mod*ifact[n-k]%mod;
}
ll A[N];

void init(){
    fact[0] = 1;
    for(int i = 1; i < N; ++i)
        fact[i] = fact[i-1]*i%mod;
    ifact[N-1] = inv(fact[N-1]);
    for(int i = N-1; i >= 1; --i)
        ifact[i-1] = ifact[i]*i%mod;
    A[0] = 1;
    A[1] = 1;
    for(int n = 1; n < N-1; ++n){
        for(int k = 0; k <= n; ++k)
            A[n+1] += C(n, k)*A[k]%mod*A[n-k]%mod;
        A[n+1] = (A[n+1]%mod)*inv(2)%mod;
    }
}

ll f(int n, int i, int j){
    if(j == 1)
        return n == 1;
    if(i == 1 && j == 2){
        if((n&1) == 0)
            return 0;
        return A[(n-2)];
    }
    if(mp[n].find(i) != mp[n].end() && mp[n][i].find(j) != mp[n][i].end())
        goto END;
    if(i == 1){
        if(n&1) mp[n][i][j] = f(n, 1, j-1) - f(n-1, 1, j-1);
        else mp[n][i][j] =  f(n, 1, j-1) + f(n-1, 1, j-1);
    }
    else if(i == 2)
        mp[n][i][j] = f(n, 1, j) + f(n-1, 1, j-1);
    else mp[n][i][j] = 2*f(n, i-1, j) - f(n, i-2, j) - f(n-2, i-2, j-2);
    mp[n][i][j] %= mod;
END:
    return mp[n][i][j];
}

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    init();
    cin >> n >> i >> j;
    cout << f(n, i, j);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 492 KB Output is correct
2 Correct 22 ms 492 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 492 KB Output is correct
2 Correct 22 ms 492 KB Output is correct
3 Incorrect 22 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 492 KB Output is correct
2 Correct 22 ms 492 KB Output is correct
3 Incorrect 22 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 492 KB Output is correct
2 Correct 22 ms 492 KB Output is correct
3 Incorrect 22 ms 492 KB Output isn't correct
4 Halted 0 ms 0 KB -