Submission #1290952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290952		Gray	Kangaroo (CEOI16_kangaroo)	C++20	6 / 100	1 ms	572 KiB

kangaroo

#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
#define ll int
#define ld long double
#define mp make_pair
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll INF = 2e9;
const ll MOD = 1e9+7;

void solve(){
    ll n, s, f; cin >> n >> s >> f;
    if (s>f) swap(s, f);
    vector<vector<ll>> dp(n+1, vector<ll>(n+1));
    dp[0][0]=1;
    for (ll i=1; i<=n; i++){
        for (ll j=0; j<=n; j++){
            if (i<s){
                if (j+1<=n) dp[i][j]=dp[i-1][j+1]*(j+1)%MOD*j%MOD;
                if (j-1>=0) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
            }else if (i==s){
                dp[i][j]=dp[i-1][j]*(j)%MOD;
                // if (j-1>=0) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
            }else if (i>s and i<f){
                if (j+1<=n) dp[i][j]=dp[i-1][j+1]*j%MOD*j%MOD;
                if (j-1>=0) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
            }else if (i==f){
                if (n%2==0){
                    dp[i][j] = dp[i-1][j];
                }else{
                    if (j+1<=n) dp[i][j] = dp[i-1][j+1]*(j)%MOD;
                }
            }else{
                if (j+1<=n) dp[i][j]=dp[i-1][j+1]*(j+1)%MOD*j%MOD;
                if (j-1>=0) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
            }
        }
    }
    // for (ll i=0; i<=n; i++){
    //     for (ll j=0; j<=n; j++){
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << ln;
    // }
    ll res=dp[n-1][1];
    dp.assign(n+1, vector<ll>(n+1, 0));
    dp[0][0]=1;
    for (ll i=1; i<=n; i++){
        for (ll j=0; j<=n; j++){
            if (i<s){
                if (j+1<=n) dp[i][j]=dp[i-1][j+1]*(j+1)%MOD*j%MOD;
                if (j-1>=0) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
            }else if (i==s){
                // dp[i][j]=dp[i-1][j]*(j)%MOD;
                if (j-1>=0) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
            }else if (i>s and i<f){
                if (j+1<=n) dp[i][j]=dp[i-1][j+1]*j%MOD*j%MOD;
                if (j-1>=0) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
            }else if (i==f){
                if (n%2){
                    dp[i][j] = dp[i-1][j];
                }else{
                    if (j+1<=n) dp[i][j] = dp[i-1][j+1]*(j)%MOD;
                }
            }else{
                if (j+1<=n) dp[i][j]=dp[i-1][j+1]*(j+1)%MOD*j%MOD;
                if (j-1>=0) dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD;
            }
        }
    }
    // for (ll i=0; i<=n; i++){
    //     for (ll j=0; j<=n; j++){
    //         cout << dp[i][j] << ' ';
    //     }
    //     cout << ln;
    // }
    /*
     * dp[i][x] => dp[i-1][x+1]*(x+1)*x+dp[i-1][x-1];
     *
     */
     cout << (res+dp[n-1][1])%MOD << ln;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll t=1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

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