Submission #1198242

#TimeUsernameProblemLanguageResultExecution timeMemory
1198242aykhn캥거루 (CEOI16_kangaroo)C++20
0 / 100
0 ms324 KiB
#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 3e3 + 5;
const int mod = 1e9 + 7;

void _()
{
  int n, a, b;
  cin >> n >> a >> b;
  vector<int> dp(n + 1, 0), ndp;
  dp[0] = 1;
  for (int val = 0; val < n; val++)
  {
    ndp = vector<int>(n + 1, 0);
    for (int c = 0; c <= n; c++)
    {
      if (!dp[c]) continue;
      if (val == a || val == b)
      {
        if (c) ndp[c] = (ndp[c] + dp[c]) % mod;
        ndp[c + 1] = (ndp[c + 1] + dp[c]) % mod;
      }
      else
      {
        int c1 = c + 1 - (a <= c) - (b <= c);
        int c2 = 2 * c - (a <= c) - (b <= c);
        ndp[c + 1] = (ndp[c + 1] + dp[c] * c1 % mod) % mod;
        if (c > 0) ndp[c - 1] = (ndp[c - 1] + dp[c] * c2 % mod) % mod;  
      }
    }
    swap(ndp, dp);
  }
  cout << dp[1] << '\n';
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) _();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...