Submission #1118215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118215		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	47 ms	31816 KiB

kangaroo

#include<bits/stdc++.h>
#define ll  long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll dp[2005][2005];
const ll mod=1e9+7;
ll n,cs,cf,f;
int main(){
    fast;
    cin>>n>>cs>>cf;
    dp[0][0]=1;
    for(ll i=1;i<=n;i++){
        if(i==cs || i==cf) f++;
        for(ll j=1;j<=n;j++){
            if(i==cs || i==cf){
                dp[i][j]=((dp[i][j]+dp[i-1][j-1])%mod+(dp[i-1][j]%mod));
            }
            else{
                dp[i][j]=(dp[i][j]+(dp[i-1][j-1]*(j-f))%mod)+((dp[i-1][j+1]*(j))%mod);
            }
            dp[i][j]%=mod;
        }
    }
    cout<<dp[n][1]%mod;

}

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