Submission #129463

#	Time	Username	Problem	Language	Result	Execution time	Memory
129463		cuiaoxiang	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	97 ms	16328 KiB

kangaroo

#define _USE_MATH_DEFINES
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;

const int N = 2e3 + 10;
int dp[N][N];

void add(int& x, int y) {
  x += y;
  if (x >= MOD) x -= MOD;
}

int n, s, t;
int solve(int at, int k) {
  // trace(at, k);
  if (at == n - 1) return k == 0 ? 1 : 0;
  int& ret = dp[at][k];
  if (ret >= 0) return ret;
  ret = 0;
  if (at == s) {
    // add left
    add(ret, solve(at + 1, k));
    // add left and touch a component
    if (k > 0) add(ret, (int64)k * solve(at + 1, k - 1) % MOD);
    return ret;
  }
  if (at == t) {
    // add right
    add(ret, solve(at + 1, k));
    // add right and touch a component
    if (k > 0) add(ret, (int64)k * solve(at + 1, k - 1) % MOD);
    return ret;
  }
  // connect left end and a component
  if (at > s && k > 0) add(ret, (int64)k * solve(at + 1, k - 1) % MOD);
  // connect right end and a component
  if (at > t && k > 0) add(ret, (int64)k * solve(at + 1, k - 1) % MOD);
  // new component
  add(ret, solve(at + 1, k + 1));
  // connect 2 components
  if (k >= 2) add(ret, (int64)k * (k - 1) * solve(at + 1, k - 1) % MOD);
  return ret;
}

int main() {
  scanf("%d%d%d", &n, &s, &t);
  --s; --t;
  memset(dp, 255, sizeof(dp));
  int ret = solve(0, 0);
  printf("%d\n", ret);
  return 0;
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &s, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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