제출 #1118226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118226		vjudge1	캥거루 (CEOI16_kangaroo)	C++17	100 / 100	35 ms	31868 KiB

kangaroo

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

#define int long long
#define ld double

const int INF = 1e18;
const int mod = 1e9 + 7;

signed main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int n, s , f;
   cin >> n >> s >> f;
   vector < vector < int > > dp(n + 1 , vector < int > (n + 1));
   dp[1][1] = 1;
   int fixed = 0;
   for(int i = 1;i <= n;i++)
   {
       fixed += (i == s or i == f);
       for(int j = 1;j < i;j++)
       {
           if(i == s or i == f)
           {
               dp[i][j + 1] = (dp[i][j + 1] + dp[i - 1][j]) % mod;
               dp[i][j] = (dp[i][j] + dp[i - 1][j]) % mod;
           }
           else
           {
               dp[i][j + 1] = (dp[i][j + 1] + (dp[i - 1][j] * (j + 1 - fixed))) % mod;
               dp[i][j - 1] = (dp[i][j - 1] + (dp[i - 1][j] * (j - 1))) % mod;
           }
       }
   }
   cout << dp[n][1] << endl;
}

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