結果

問題 No.834 Random Walk Trip
ユーザー pekempeypekempey
提出日時 2019-05-25 16:16:20
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 52 ms / 2,000 ms
コード長 1,663 bytes
コンパイル時間 623 ms
コンパイル使用メモリ 75,680 KB
実行使用メモリ 15,172 KB
最終ジャッジ日時 2024-09-17 15:05:19
合計ジャッジ時間 1,549 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 1 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 1 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 1 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 4 ms
6,940 KB
testcase_18 AC 9 ms
6,944 KB
testcase_19 AC 41 ms
15,172 KB
testcase_20 AC 8 ms
6,940 KB
testcase_21 AC 38 ms
15,020 KB
testcase_22 AC 2 ms
6,940 KB
testcase_23 AC 42 ms
12,500 KB
testcase_24 AC 4 ms
6,940 KB
testcase_25 AC 52 ms
15,096 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

const int MOD = 1000000007;

struct mint {
  int n;
  mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return a.n == 0 || b.n == 0 ? 0 : (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

vector<mint> F_{1, 1}, R_{1, 1}, I_{0, 1};

void check_fact(int n) {
  for (int i = I_.size(); i <= n; i++) {
    I_.push_back(I_[MOD % i] * (MOD - MOD / i));
    F_.push_back(F_[i - 1] * i);
    R_.push_back(R_[i - 1] * I_[i]);
  }
}

mint I(int n) { check_fact(n); return I_[n]; }
mint F(int n) { check_fact(n); return n < 0 ? 0 : F_[n]; }
mint R(int n) { check_fact(n); return n < 0 ? 0 : R_[n]; }
mint C(int n, int r) { return F(n) * R(n - r) * R(r); }
mint P(int n, int r) { return F(n) * R(n - r); }
mint H(int n, int r) { return n == 0 ? (r == 0) : C(n + r - 1, r); }

int modulo(int x, int y) {
  x %= y;
  if (x < 0) x += y;
  return x;
}

int main() {
  int N, M;
  cin >> N >> M;
  if (N == 1) {
    cout << 1 << '\n';
    return 0;
  }
  mint ans;
  for (int i = -M; i <= M; i++) {
    if (modulo(i, N*2) == 0 || modulo(i, N*2) == N*2-1) {
      int d = abs(i);
      if ((M + d) % 2 == 0) {
        ans += C(M, (M + d) / 2);
      }
    }
  }
  cout << ans.n << '\n';
}
0