Submission #1224699


Source Code Expand

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(s) ((int) ((s).size()))

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

typedef long long ll;
typedef long double ld;

const int inf = (int) 1.01e9;
const ld eps = 1e-11;
const ld pi = acos(-1.0L);

mt19937 mrand(random_device{} ());
int rnd(int x) {
  return mrand() % x;
}

const int mod = (int) 1e9 + 7;

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

int sum(int x, int y) {
  add(x, y);
  return x;
}

int mult(int x, int y) {
  return (ll) x * y % mod;
}

int power(int x, ll p) {
  int res = 1;
  while (p) {
    if (p & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
    p >>= 1;
  }
  return res;
}

int inv(int x) {
  return power(x, mod - 2);
}

void precalc() {
}

int n, m;

bool read() {
  if (scanf("%d%d", &n, &m) < 2) {
    return false;
  }
  return true;
}

void solve() {
  int res = 0;
  vector<int> c(2 * m + 1);
  c[0] = 1;
  for (int i = 1; i <= 2 * m; i++) {
    c[i] = mult(c[i - 1], 2 * m - i + 1);
    c[i] = mult(c[i], inv(i));
  }
  for (int diff = n - 1; diff <= n; diff++) {
    int cur = 0;
    int step = 2 * (diff + 1);
    vector<int> v(step);
    for (int i = 0; i <= 2 * m; i++) {
      add(v[i % step], c[i]);
    }
    int val = 0;
    for (int i = m; i <= m + diff; i++) {
      add(val, v[i % step]);
    }
    for (int i = m + step / 2; i <= m + step / 2 + diff; i++) {
      add(val, mod - v[i % step]);
    }
    for (int it = 0; it <= diff; it++) {
      add(cur, val);
      add(val, v[((m - it - 1) % step + step) % step]);
      add(val, mod - v[(m + diff - it) % step]);
      add(val, mod - v[((m - it - 1 + step / 2) % step + step) % step]);
      add(val, v[(m + diff - it + step / 2) % step]);
    }
    if ((diff - n) & 1) {
      add(res, mod - cur);
    } else {
      add(res, cur);
    }
  }
  printf("%d\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen("text.in", "r", stdin));
  assert(freopen("text.out", "w", stdout));
#endif

  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time: %.3f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}

Submission Info

Submission Time
Task D - Piling Up
User StanislavErshov
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2424 Byte
Status AC
Exec Time 2 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 33
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 2 ms 256 KB
subtask_1_01.txt AC 2 ms 256 KB
subtask_1_02.txt AC 2 ms 256 KB
subtask_1_03.txt AC 2 ms 256 KB
subtask_1_04.txt AC 2 ms 256 KB
subtask_1_05.txt AC 2 ms 256 KB
subtask_1_06.txt AC 2 ms 256 KB
subtask_1_07.txt AC 2 ms 256 KB
subtask_1_08.txt AC 2 ms 256 KB
subtask_1_09.txt AC 2 ms 256 KB
subtask_1_10.txt AC 2 ms 256 KB
subtask_1_11.txt AC 2 ms 256 KB
subtask_1_12.txt AC 2 ms 256 KB
subtask_1_13.txt AC 2 ms 256 KB
subtask_1_14.txt AC 2 ms 256 KB
subtask_1_15.txt AC 2 ms 256 KB
subtask_1_16.txt AC 2 ms 256 KB
subtask_1_17.txt AC 2 ms 256 KB
subtask_1_18.txt AC 2 ms 256 KB
subtask_1_19.txt AC 2 ms 256 KB
subtask_1_20.txt AC 2 ms 256 KB
subtask_1_21.txt AC 2 ms 256 KB
subtask_1_22.txt AC 2 ms 256 KB
subtask_1_23.txt AC 2 ms 256 KB
subtask_1_24.txt AC 2 ms 256 KB
subtask_1_25.txt AC 1 ms 256 KB
subtask_1_26.txt AC 2 ms 256 KB
subtask_1_27.txt AC 1 ms 256 KB