結果
問題 | No.660 家を通り過ぎないランダムウォーク問題 |
ユーザー |
![]() |
提出日時 | 2018-03-16 17:19:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 1,163 bytes |
コンパイル時間 | 1,439 ms |
コンパイル使用メモリ | 158,468 KB |
実行使用メモリ | 19,072 KB |
最終ジャッジ日時 | 2024-12-21 14:30:40 |
合計ジャッジ時間 | 9,282 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 45 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:46:13: warning: iteration 1000000 invokes undefined behavior [-Waggressive-loop-optimizations] 46 | fac[i+1]=fac[i]*(i+1)%mod; | ^ main.cpp:10:39: note: within this loop 10 | #define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) | ^ main.cpp:11:18: note: in expansion of macro ‘repl’ 11 | #define rep(i,n) repl(i,0,n) | ^~~~ main.cpp:45:3: note: in expansion of macro ‘rep’ 45 | rep(i,1000001){ | ^~~
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> P; #define fi first #define se second #define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++) #define rep(i,n) repl(i,0,n) #define all(x) (x).begin(),(x).end() #define dbg(x) cout<<#x"="<<x<<endl #define mmax(x,y) (x>y?x:y) #define mmin(x,y) (x<y?x:y) #define maxch(x,y) x=mmax(x,y) #define minch(x,y) x=mmin(x,y) #define uni(x) x.erase(unique(all(x)),x.end()) #define exist(x,y) (find(all(x),y)!=x.end()) #define bcnt __builtin_popcount #define INF 1e16 #define mod 1000000007 ll mod_pow(ll x,ll n){ ll res=1; while(n>0){ if(n&1)res=res*x%mod; x=x*x%mod; n>>=1; } return res; } ll n; ll fac[1000001],finv[1000001]; ll comb(ll a,ll r){ if(a<0||r<0||a-r<0)return 0; return (fac[a]*finv[r]%mod)*finv[a-r]%mod; } int main(){ fac[0]=1; rep(i,1000001){ fac[i+1]=fac[i]*(i+1)%mod; finv[i]=mod_pow(fac[i],mod-2); } cin>>n; ll res=1; for(ll x=n+1,y=1;x+y<=2*n;x++,y++){ ll xx=x-1,yy=y; ll rx=xx-n,ry=yy+n; (res+=comb(x+y-1,x-1)-comb(rx+ry,rx)+mod)%=mod; } cout<<res<<endl; return 0; }