Submission #1001526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001526		vjudge1	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	14 ms	29792 KiB

kangaroo

#include<bits/stdc++.h>
using namespace std;
long long dp[2010][2010],M=1e9+7;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,a,b;
    cin>>n>>a>>b;
    dp[0][0]=1;
    if(a>b)swap(a,b);
    for(int i=1;i<a;i++) for(int j=1;j<=i;j++)
        dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])*j%M;
    for(int j=1;j<=a;j++)
        dp[a][j]=(dp[a-1][j-1]+dp[a-1][j])%M;
    for(int i=a;++i<b;) for(int j=1;j<=i;j++)
        dp[i][j]=(dp[i-1][j-1]*(j-1)+dp[i-1][j+1]*j)%M;
    for(int j=1;j<=b;j++)
        dp[b][j]=(dp[b-1][j-1]+dp[b-1][j])%M;
    for(int i=b;i++<n;) for(int j=1;j<=i;j++)
        dp[i][j]=(dp[i-1][j-1]*max(0,j-2)+dp[i-1][j+1]*j)%M;
    cout<<dp[n][1]<<'\n';
}

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