Submission #1278799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278799		k12_khoi	캥거루 (CEOI16_kangaroo)	C++17	100 / 100	16 ms	14216 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

const int N=2e3+5;
const int mod=1e9+7;

int n,start,goal;
int dp[N][N];

int add(int x,int y)
{
    if (y>=mod) y-=mod;

    x+=y;
    if (x>=mod) x-=mod;

    return x;
}

int mul(int x,int y)
{
    return 1LL*x*y%mod;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> start >> goal;

    dp[1][1]=1;
    for (int i=2;i<=n;i++)
    for (int j=1;j<=i;j++)
    if (i==start or i==goal) dp[i][j]=add(dp[i-1][j],dp[i-1][j-1]);
    else
    {
        dp[i][j]=mul(dp[i-1][j+1],j);

        if (j-(i>start)-(i>goal)>0)
            dp[i][j]=add(dp[i][j],mul(dp[i-1][j-1],j-(i>start)-(i>goal)));
    }

    cout << dp[n][1];
}

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