Submission #1102475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102475		underwaterkillerwhale	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	32 ms	16376 KiB

kangaroo

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e3 + 7;
const int Mod = 1e9 + 7;///lon
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 450;

inline void Add (int &A, int B) {
    A += B;
    if (A >= Mod) A -= Mod;
}

int n, St, Ed;
int dp[N][N];

void solution () {
    cin >> n >> St >> Ed;
    auto solve = [] (int St, int Ed) {
        memset(dp, 0, sizeof dp);
        dp[1][0] = 1;
        rep (i, 2, n) {
            if (i != St && i != Ed) {
                rep (j, 0, i - 1) {
                    if (j > 0)
                        dp[i][j] = 1LL * dp[i - 1][j - 1] * (j + 1 - (i > St) - (i > Ed)) % Mod;
                    Add(dp[i][j], 1LL * dp[i - 1][j + 1] * (j + 1) % Mod);
                }
            }
            else {
                if (i == St) {
                    rep (j, 0, i - 1) {
                        if (j > 0) dp[i][j] = dp[i - 1][j - 1];
                    }
                }
                else {
                    rep (j, 0, i - 1) {
                        if (n % 2 == 0) dp[i][j] = dp[i - 1][j];
                        else if (j > 0) dp[i][j] = dp[i - 1][j - 1];
                    }
                }
            }
        }
        return dp[n][0];
    };
    cout << (solve (St, Ed) + solve(n - St + 1, n - Ed + 1)) % Mod <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +11

7 9
1 5 3 4 8 3 2
7 4 8 3 2 3 1

ko gan gtri bien co the cut
bien doi operation update doan thanh update phan tu tren mang hieu de de quan sat mo hinh bai toan hon
*/

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