제출 #1278795

#제출 시각아이디문제언어결과실행 시간메모리
1278795k12_khoi캥거루 (CEOI16_kangaroo)C++17
6 / 100
1 ms576 KiB
#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)-(j>goal)>0)
            dp[i][j]=add(dp[i][j],mul(dp[i-1][j-1],j-(i>start)-(j>goal)));
    }

    cout << dp[n][1];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...