Submission #988598

#	Time	Username	Problem	Language	Result	Execution time	Memory
988598		steveonalex	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	20 ms	16472 KiB

kangaroo

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ll mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
 
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b) {a = b; return true;}
        return false;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b) {a = b; return true;}
        return false;
    }
 
template <class T>
    void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
        for(auto item: container) out << item << separator;
        out << finish;
    }
 
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 2007;
const int MOD = 1e9 + 7;

void add(int &a, int b){
    a += b;
    if (a >= MOD) a -= MOD;
}

int n, s, f; 
int dp[N][N];

namespace Odd{
    void solve(){
        int ans=  0;
        s--; f--;
        for(int iteration = 0; iteration <= 1; ++iteration){
            if (s != n-1 && f != n-1){
                memset(dp, 0, sizeof dp);
                dp[0][0] = 1;
                for(int i = 0; i<n-1; ++i) {
                    if (i == s || i == f){
                        for(int j = 0; j< n; ++j) add(dp[i+1][j], dp[i][j]);
                        continue;
                    }
                    int edge_cnt = (i >= s) + (i >= f);
                    for(int j = 0; j< n; ++j) if (dp[i][j]){
                        add(dp[i+1][j+1], dp[i][j]);
                        if (j > 0 && j + edge_cnt > 1){
                            int mul = j * (j-1) + edge_cnt * j;
                            add(dp[i+1][j-1], 1LL * mul * dp[i][j] % MOD);
                        }
                    }
                }
                add(ans, dp[n-1][0]);
            }

            s = n-1-s, f = n-1-f;
        }

        cout << ans << "\n";

        exit(0);
    }
}

namespace Even{
    void solve(){
        int ans = 0;
        s--; f--;
        for(int iteration = 0; iteration <= 1; ++iteration){
            if (s != n-1 && f != 0){
                memset(dp, 0, sizeof dp);
                dp[0][0] = 1;
                for(int i = 0; i<n; ++i) {
                    if (i == s){
                        for(int j = 0; j< n; ++j) add(dp[i+1][j], dp[i][j]);
                        continue;
                    }
                    if (i == f){
                        for(int j = 1; j<n; ++j) if (dp[i][j]){
                            add(dp[i+1][j-1], 1LL * dp[i][j] * j % MOD);
                        }
                        continue;
                    }
                    int edge_cnt = (i >= s) + (i >= f);
                    for(int j = 0; j< n; ++j) if (dp[i][j]){
                        add(dp[i+1][j+1], dp[i][j]);
                        if (j > 0 && j + edge_cnt > 1){
                            int mul = j * (j-1) + edge_cnt * j;
                            add(dp[i+1][j-1], 1LL * mul * dp[i][j] % MOD);
                        }
                    }
                }
                add(ans, dp[n-1][0]);
            }

            s = n-1-s, f = n-1-f;
        }

        cout << ans << "\n";

        exit(0);
    }
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> s >> f;
    if (n % 2 == 1) Odd::solve();
    else Even::solve();


    return 0;
}

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