結果
問題 |
No.660 家を通り過ぎないランダムウォーク問題
|
ユーザー |
|
提出日時 | 2025-08-06 13:14:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 1,296 bytes |
コンパイル時間 | 1,835 ms |
コンパイル使用メモリ | 195,244 KB |
実行使用メモリ | 9,696 KB |
最終ジャッジ日時 | 2025-08-06 13:14:11 |
合計ジャッジ時間 | 4,147 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
ソースコード
#include <bits/stdc++.h> #define int ll #define fi first #define endl '\n' #define il inline #define se second #define pb push_back #define INF 0x3f3f3f3f using namespace std; typedef long long ll; typedef pair<int, int> pii; #ifdef ONLINE_JUDGE #define debug(...) 0 #else #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr) #endif const int N = 4e5 + 10; const int mod = 1e9 + 7; int fac[N], in[N]; int qpow(int a, int p) { int res = 1; while (p) { if (p & 1) res = res * a % mod; a = a * a % mod; p >>= 1; } return res; } il int inv(int x) { return qpow(x, mod - 2); } int C(int n, int m) { if (m < 0 || m > n) return 0; return ((fac[n] * in[m] % mod) * in[n - m]) % mod; } int n; signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n; fac[0] = 1; for (int i = 1; i <= 2 * n; i++) fac[i] = fac[i - 1] * i % mod; in[2 * n] = inv(fac[2 * n]); for (int i = 2 * n - 1; ~i; i--) in[i] = in[i + 1] * (i + 1) % mod; int ans = 0; for (int i = n; i <= 2 * n; i += 2) { int y = (i - n) / 2, x = i - y - 1; int d = C(x + y, x); d = (d - C(x + y, y - 1) + mod) % mod; ans = (ans + d) % mod; } cout << ans << endl; return 0; }