結果
問題 | No.834 Random Walk Trip |
ユーザー |
|
提出日時 | 2019-05-27 00:32:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 1,465 bytes |
コンパイル時間 | 1,607 ms |
コンパイル使用メモリ | 169,132 KB |
実行使用メモリ | 18,932 KB |
最終ジャッジ日時 | 2024-09-17 15:24:40 |
合計ジャッジ時間 | 2,671 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long pow_mod(long long b, long long p, long long mod = 1'000'000'007){ long long ret = 1; while (p){ if (p & 1) ret = (ret * b) % mod; b = (b * b) % mod; p >>= 1; } return ret; } class ModuloMath{ private: long long N; long long mod; public: vector<long long> fac; vector<long long> invfac; ModuloMath(long long N, long long mod = 1'000'000'007): N{N}, mod{mod}, fac(N + 1, 1), invfac(N + 1, 1){ for (long long i = 1; i <= N; ++i) fac[i] = (fac[i - 1] * i) % mod; invfac[N] = pow_mod(fac[N], mod - 2, mod); for (long long i = N; i != 1; --i) invfac[i - 1] = (invfac[i] * i) % mod; } long long nCr(long long n, long long r){return (r > n or r < 0) ? 0 : (fac[n] * invfac[n - r] % mod * invfac[r] % mod);} long long nPr(long long n, long long r){return (r > n or r < 0) ? 0 : (fac[n] * invfac[n - r] % mod);} long long nHr(long long n, long long r){return nCr(n + r - 1, r);} }; constexpr long long mod = 1e9+7; int main(){ int N, M; cin >> N >> M; if (N == 1){ cout << 1 << endl; return 0; } ModuloMath mm(M); long long ans = 0; int adj = M & 1; for (int a = 0; a <= M; ++a){ int amb = 2 * a - M + adj; if ((abs(amb) % (2 * N)) == 0){ ans += mm.nCr(M, a); ans %= mod; } } cout << ans << endl; return 0; }