結果

問題 No.660 家を通り過ぎないランダムウォーク問題
ユーザー beetbeet
提出日時 2018-03-02 22:55:59
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 2,053 bytes
コンパイル時間 2,102 ms
コンパイル使用メモリ 145,484 KB
実行使用メモリ 8,328 KB
最終ジャッジ日時 2023-09-04 05:40:57
合計ジャッジ時間 6,274 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 16 ms
8,152 KB
testcase_01 AC 16 ms
8,040 KB
testcase_02 AC 16 ms
8,208 KB
testcase_03 AC 17 ms
8,028 KB
testcase_04 AC 16 ms
8,208 KB
testcase_05 AC 16 ms
8,324 KB
testcase_06 AC 16 ms
8,076 KB
testcase_07 AC 16 ms
8,104 KB
testcase_08 AC 16 ms
8,036 KB
testcase_09 AC 16 ms
8,016 KB
testcase_10 AC 16 ms
8,024 KB
testcase_11 AC 16 ms
8,032 KB
testcase_12 AC 16 ms
8,028 KB
testcase_13 AC 16 ms
8,028 KB
testcase_14 AC 16 ms
8,016 KB
testcase_15 AC 16 ms
8,168 KB
testcase_16 AC 16 ms
8,020 KB
testcase_17 AC 16 ms
8,104 KB
testcase_18 AC 16 ms
8,024 KB
testcase_19 AC 16 ms
8,328 KB
testcase_20 AC 16 ms
8,084 KB
testcase_21 AC 16 ms
8,080 KB
testcase_22 AC 16 ms
8,028 KB
testcase_23 AC 16 ms
8,172 KB
testcase_24 AC 16 ms
8,076 KB
testcase_25 AC 16 ms
8,072 KB
testcase_26 AC 17 ms
8,136 KB
testcase_27 AC 17 ms
8,076 KB
testcase_28 AC 16 ms
8,100 KB
testcase_29 AC 18 ms
8,328 KB
testcase_30 AC 18 ms
8,088 KB
testcase_31 AC 18 ms
8,204 KB
testcase_32 AC 20 ms
8,208 KB
testcase_33 AC 20 ms
8,012 KB
testcase_34 AC 21 ms
8,080 KB
testcase_35 AC 33 ms
8,032 KB
testcase_36 AC 33 ms
8,020 KB
testcase_37 AC 33 ms
8,024 KB
testcase_38 AC 60 ms
8,028 KB
testcase_39 AC 62 ms
8,080 KB
testcase_40 AC 64 ms
8,084 KB
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using Int = long long;

#define MOD 1000000007
#define MAX_P 200005
Int fact[MAX_P],inv[MAX_P],finv[MAX_P];;
Int extgcd(Int a,Int b,Int& x,Int& y){
  Int d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}
Int mod_inverse(Int a,Int mod){
  Int x,y;
  extgcd(a,mod,x,y);
  return (mod+x%mod)%mod;
}

Int mod_pow(Int x,Int n,Int mod){
  Int res=1;
  while(n){
    if(n&1) (res*=x)%=mod;
    (x*=x)%=mod;
    n>>=1;
  }
  return res;
}

Int mod_inverse2(Int a,Int mod){
  return mod_pow(a,mod-2,mod);
}

void init(Int mod){
  fact[0]=1;
  for(Int i=1;i<MAX_P;i++)
    fact[i]=(fact[i-1]*i)%mod;

  inv[1]=1;
  for(Int i=2;i<MAX_P;i++)
    inv[i]=inv[mod%i]*(mod-mod/i)%mod;
  
  finv[0]=1;
  for(Int i=1;i<MAX_P;i++)
    finv[i]=finv[i-1]*inv[i]%mod;
}

Int mod_fact(Int n,Int mod,Int& e){
  e=0;
  if(n==0) return 1;
  Int res=mod_fact(n/mod,mod,e);
  e+=n/mod;
  if(n/mod%2!=0)return res*(mod-fact[n%mod]) %mod;
  return res*fact[n%mod]%mod;
}

Int mod_comb(Int n,Int k,Int mod){
  if(n==k||k==0) return 1;
  Int e1,e2,e3;
  Int a1=mod_fact(n,mod,e1),a2=mod_fact(k,mod,e2),a3=mod_fact(n-k,mod,e3);
  if(e1>e2+e3) return 0;
  return a1*mod_inverse(a2*a3%mod,mod)%mod;
}

Int mod_comb2(Int n,Int k,Int mod){
  Int res=1;
  for(Int i=0;i<k;i++){
    res*=(n-i)%mod;
    res%=mod;
    res*=mod_inverse(i+1,mod);
    res%=mod;
  }
  return res;
}

//only for prime mod
Int mod_comb3(Int n,Int k,Int mod){
  if(k<0||k>n) return 0;
  return fact[n]*finv[k]%mod*finv[n-k]%mod;
}

Int montmort(Int n,Int mod){
  Int res=0,inv=1;
  for(Int k=2;k<=n;k++){
    (inv*=mod_inverse(k,mod))%=mod;
    if(k%2) (res+=mod-inv)%=mod;
    else (res+=inv)%=mod;
  }
  for(Int i=1;i<=n;i++)
    (res*=i)%=mod;
  return res;
}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  init(MOD);
  Int ans=1;
  for(Int i=1;i*2<=n;i++){
    Int a=i,b=n-1+i;
    ans+=mod_comb(a+b,a,MOD);
    ans%=MOD;
    ans+=MOD-mod_comb(a+b,a-1,MOD);
    ans%=MOD;
  }
  cout<<ans<<endl;
  return 0;
}
0