Submission #569627

#TimeUsernameProblemLanguageResultExecution timeMemory
569627Abrar_Al_SamitKangaroo (CEOI16_kangaroo)C++17
0 / 100
15 ms31636 KiB
#include<bits/stdc++.h>
using namespace std;

const int MX = 2002;
const int Mod = 1e9 + 7;

int add(int a, int b) {
  a += b;
  if(a>=Mod) a -= Mod;
  return a;
}
int mul(int a, int b) {
  return (a * 1LL * b) % Mod;
}
int n, cs, cf;
int dp[MX][MX/2][2][2];

int solve(int i, int j, bool ad1, bool ad2) {
  if(i==n-1) return 1;
  int &ret = dp[i][j][ad1][ad2];
  if(ret!=-1) return ret;
  if(i==cs || i==cf) return ret = solve(i+1, j, ad1, ad2);
  ret = 0;
  //new component
  if(j+1<=(n+1)/2) ret = add(ret, mul(j-1, solve(i+1, j+1, ad1, ad2)));
  //merge
  if(j>2) ret = add(ret, mul(j-1, solve(i+1, j-1, ad1, ad2)));

  //extend
  if(!ad1 && i<cs) ret = add(ret, solve(i+1, j, 1, ad2));
  if(!ad2 && i<cf) ret = add(ret, solve(i+1, j, ad1, 1));

  return ret;
}
void PlayGround() {
  cin>>n>>cs>>cf;
  memset(dp, -1, sizeof dp);
  cout<<solve(1, 2, 0, 0)<<'\n';
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  PlayGround();
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...