結果
問題 |
No.660 家を通り過ぎないランダムウォーク問題
|
ユーザー |
![]() |
提出日時 | 2025-08-25 11:29:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 18 ms / 2,000 ms |
コード長 | 1,307 bytes |
コンパイル時間 | 2,080 ms |
コンパイル使用メモリ | 193,920 KB |
実行使用メモリ | 19,252 KB |
最終ジャッジ日時 | 2025-08-25 11:29:31 |
合計ジャッジ時間 | 4,654 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define file(x,y) freopen(x,"r",stdin),freopen(y,"w",stdout); #define tup tuple<int,int,int> #define pii pair<int,int> #define bit(x) bitset<x> #define pb emplace_back #define i12 __int128_t #define mt make_tuple #define mp make_pair const int maxn=1e6+10; const int mod=1e9+7; int frac[maxn],invf[maxn]; int n; int power(int a,int b,int p) { int tar=1ll; for(; b; b>>=1,a=1ll*a*a%p) if(b&1) tar=1ll*tar*a%p; return tar; } int C(int n,int m) { return frac[n]*invf[m]%mod*invf[n-m]%mod; } int calc(int x) { int left=x-n; if(left&1) return 0; left>>=1; int right=x-1-left; return C(left+right,right)-C(left+right,left-1); } void work() { /* Code */ cin>>n; int tar=0; for(int i=n; i<=2*n; i++) (tar+=calc(i))%=mod; cout<<(tar%mod+mod)%mod<<'\n'; return; } signed main() { // file(".in",".out"); ios::sync_with_stdio(false); cin.tie(0); int t,stTime=clock(); t=1; frac[0]=1; for(int i=1; i<maxn; i++) frac[i]=frac[i-1]*i%mod; invf[maxn-1]=power(frac[maxn-1],mod-2,mod); for(int i=maxn-2; ~i; i--) invf[i]=invf[i+1]*(i+1)%mod; while(t--) work(); // cerr<<"Time : "<<(double)(clock()-stTime)/CLOCKS_PER_SEC<<'\n'; return 0; } // Cellinia Texas.