結果
問題 |
No.660 家を通り過ぎないランダムウォーク問題
|
ユーザー |
![]() |
提出日時 | 2025-07-24 21:28:42 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 1,247 bytes |
コンパイル時間 | 3,274 ms |
コンパイル使用メモリ | 276,072 KB |
実行使用メモリ | 9,696 KB |
最終ジャッジ日時 | 2025-07-24 21:28:47 |
合計ジャッジ時間 | 4,863 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
ソースコード
#include <bits/stdc++.h> #define int long long //#define USE_FREOPEN //#define MUL_TEST #define FILENAME "walk" using namespace std; constexpr int mod = 1e9 + 7; int fac[400005], inv[400005]; int ksm(int a, int b) { int res = 1, t = a; while (b) { if (b & 1) res = res * t % mod; t = t * t % mod; b >>= 1; } return res; } int C(int n, int m) { if (m < 0 || m > n) return 0; return ((fac[n] * inv[m] % mod) * inv[n - m] % mod); } void solve() { int n; cin >> n; fac[0] = 1; for (int i = 1; i <= 2 * n; i++) fac[i] = fac[i - 1] * i % mod; inv[2 * n] = ksm(fac[2 * n], mod - 2); for (int i = 2 * n - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % mod; int ans = 0; for (int i = n; i <= 2 * n; i += 2) { int y = (i - n) / 2; int x = i - y - 1; // cerr << i << ' ' << x << ' ' << y << ' ' << C(x + y, x) << '\n'; int d = C(x + y, x); d = (d - C(x + y, y - 1) + mod) % mod; ans = (ans + d) % mod; } cout << ans << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #ifdef USE_FREOPEN freopen(FILENAME ".in", "r", stdin); freopen(FILENAME ".out", "w", stdout); #endif int _ = 1; #ifdef MUL_TEST cin >> _; #endif while (_--) solve(); _^=_; return 0^_^0; }