結果
問題 | No.660 家を通り過ぎないランダムウォーク問題 |
ユーザー |
![]() |
提出日時 | 2018-03-26 00:59:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 312 ms / 2,000 ms |
コード長 | 1,148 bytes |
コンパイル時間 | 1,675 ms |
コンパイル使用メモリ | 167,696 KB |
実行使用メモリ | 11,340 KB |
最終ジャッジ日時 | 2024-06-25 06:26:10 |
合計ジャッジ時間 | 17,061 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; #define MOD 1000000007 #define MX 500005 ll fact[MX]; ll invfact[MX]; ll mod_pow(ll x, ll n, ll mod){ if(n==0) return 1; ll res = mod_pow(x * x % mod, n / 2, mod); if(n & 1) res = res * x % mod; return res; } ll mod_comb(ll n, ll k){ if(n<0 || k<0 || n<k) return 0; return (((fact[n] * invfact[k]) % MOD) * invfact[n-k]) % MOD; } void comb_init(){ fact[0] = fact[1] = 1; for(ll i=2; i<MX; i++) fact[i] = (fact[i-1] * i) % MOD; invfact[0] = invfact[1] = 1; for(ll i=2; i<MX; i++) invfact[i] = mod_pow(fact[i], MOD-2, MOD); } int main(){ comb_init(); int N; cin >> N; ll ret = 1; REP(i,1,N/2+1){ ll h = i; ll w = N-1+i; ll tmp1 = mod_comb(h+w, w); ll tmp2 = mod_comb(h-1+w+1, w+1); ll ans = (tmp1 - tmp2 + MOD)%MOD; ret += ans; ret %= MOD; } cout << ret << endl; return 0; }