結果
問題 |
No.834 Random Walk Trip
|
ユーザー |
|
提出日時 | 2019-08-02 01:28:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 188 ms / 2,000 ms |
コード長 | 835 bytes |
コンパイル時間 | 2,146 ms |
コンパイル使用メモリ | 195,876 KB |
最終ジャッジ日時 | 2025-01-07 10:31:33 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; int ipow(int v, int n, int m = MOD) { int r = 1; while (n) { if (n & 1) r = 1LL * r * v % m; v = 1LL * v * v % m; n >>= 1; } return r; } int inv(int v, int m = MOD) { return ipow(v, m - 2, m); } int main() { ios::sync_with_stdio(false); int N, M; cin >> N >> M; if (N == 1) { cout << 1 << endl; return 0; } vector<int> C_m(M + 1); C_m[0] = 1; for (int i = 0; i < M; ++i) { C_m[i + 1] = 1LL * C_m[i] * (M - i) % MOD * inv(i + 1) % MOD; } // m!/i!(m-i)! -> (m-i)/(i+1) * m!/i!(m-i)! int ans = 0; for (int i = 0; i < M + 1; ++i) { int x = i - (M - i); if (x < 0) { x = -x + 1; } if (x % (2 * N) < 2) { (ans += C_m[i]) %= MOD; } } cout << ans << endl; return 0; }