結果
問題 |
No.660 家を通り過ぎないランダムウォーク問題
|
ユーザー |
![]() |
提出日時 | 2025-07-30 20:07:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 690 bytes |
コンパイル時間 | 1,900 ms |
コンパイル使用メモリ | 195,260 KB |
実行使用メモリ | 11,468 KB |
最終ジャッジ日時 | 2025-07-30 20:07:22 |
合計ジャッジ時間 | 4,301 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
ソースコード
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define int ll const int N=5e5+7; const int mod=1e9+7; int inv[N],fac[N]; inline int ksm(int a,int b){ int res=1; while(b){ if(b&1)res=res*a%mod; a=a*a%mod;b>>=1; } return res; } inline int C(int n,int m){ if(n<m||n<0||m<0)return 0ll; return fac[n]*inv[n-m]%mod*inv[m]%mod; } signed main(){ fac[0]=1; for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod; inv[N-1]=ksm(fac[N-1],mod-2); for(int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod; inv[0]=inv[1]=1; int n;cin>>n; int res=0; for(int i=n;i<=2*n;i+=2){ int tmp=((C(i-1,i-(i-n)/2-1)-C(i-1,(i-n)/2-1))%mod+mod)%mod; (res+=tmp)%=mod; } cout<<(res%mod+mod)%mod; }