Submission #1118196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118196		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	8 ms	31836 KiB

kangaroo

// #pragma GCC optimize("Ofast,unroll-loops")

// el psy congroo
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
const int mod = 1e9 +7, sze = 2e3+23, inf = 2e9, LG = 19,pr = 31;
int dp[sze][sze];
void fast(){
    int n,a,b;
    cin>>n>>a>>b;
    dp[1][1]=1;
    for(int i =2;i<=n;i++){
        for(int j=1;j<=i;j++){
            // i,j 
            if( i==a || i==b ){
                dp[i][j] = (dp[i-1][j-1]+ dp[i-1][j] + mod)%mod;
            }
            else{
                // cout<<i<<":"<<j<<" "<<dp[i-1][j]<<" =>"<<dp[i-1][j-1]*(j- (i>a) - (i>b)) <<" "<< dp[i-1][j+1]*j<<endl;
                dp[i][j] = (
                    dp[i-1][j-1] * (j- (i>a) - (i>b))
                    + 
                    dp[i-1][j+1] * (j)
                    +
                    // dp[i-1][j] * ( i+j-1 - (i>a) - (i>b) ) * (j!=1)
                    mod)%mod;
                /*
                    new compenent:
                        dp[i-1][j-1] * ( j - (i>a) - (i>b) );
                    union compenents:
                        dp[i-1][j+1] * (j)
                    inside compenent:
                        dp[i-1][j] * ( i -1 + j ... );

        
                */
            }
            // cout<< i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    }

    putr( (dp[n][1] + mod )%mod );
}

 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1;
    // cin>>tt;
 
    while(tt--){
        fast();
    }
    return 0;
}

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