結果

問題 No.1073 無限すごろく
コンテスト
ユーザー yukudo
提出日時 2020-06-05 21:54:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,401 bytes
コンパイル時間 1,724 ms
コンパイル使用メモリ 176,892 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-12-17 14:30:16
合計ジャッジ時間 2,639 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

ll nextLong() { ll x; scanf("%lld", &x); return x;}

const ll MOD = 1e9 + 7;

#define SZ(v) ((int)(v).size())
using Array = vector<ll>;
using Matrix = vector<Array>;

Matrix zero(int N){ return Matrix(N, Array(N)); }

Matrix identity(int N) {
  Matrix A = zero(N);
  REP(i, N) A[i][i] = 1;
  return A;
}

Matrix add(const Matrix &A, const Matrix& B){
  const int N = SZ(A);
  const int M = SZ(A[0]);
  Matrix C(N, Array(M));
  REP(i, N) REP(j, M) {
    C[i][j] += A[i][j] + B[i][j];
    if (C[i][j] >= MOD) C[i][j] %= MOD;
  }
  return C;
}

Array mul(const Matrix &A, const Array &x){
  const int N = SZ(A);
  const int M = SZ(A[0]);
  Array y(N);
  REP(i, N) REP(j, M)
    y[i] += A[i][j] * x[j];
  return y;
}

// A:[N,P] * B:[P,M] = C:[N,M]
Matrix mul(const Matrix &A, const Matrix& B) {
  const int N = SZ(A);
  const int P = SZ(A[0]);
  const int M = SZ(B[0]);
  Matrix C(N, Array(M));
  REP(i, N) REP(j, M) REP(k, P) {
    C[i][j] += A[i][k] * B[k][j];
    if (C[i][j] >= MOD) C[i][j] %= MOD;
  }
  return C;
}

// O ( n^3 log e )
// Matrix pow(const Matrix& A, ll e) {
//   return e == 0 ? identity(SZ(A)) :
//     e % 2 == 0 ? pow( mul(A,A) , e/2 ) : mul(A, pow(A,e-1));
// }
Matrix pow(Matrix A, ll b) {
  Matrix C = identity(SZ(A));
  while (b > 0) {
    if ((b & 1) == 1) C = mul(C, A);
    A = mul(A, A);
    b >>= 1;
  }
  return C;
}

void print(const Matrix& A){
  REP(i, SZ(A)){
    REP(j, SZ(A[0])){
      cout << A[i][j] << " ";
    }
    cout << endl;
  }
  cout << "---------------------" << endl;
}




int main2() {
  ll N = nextLong();

  Matrix X = zero(6);

  for (int i = 0; i < 6; i++) X[0][i] = 166666668;
  for (int i = 0; i < 5; i++) X[i+1][i] = 1;
  // print(X);

  auto B = pow(X, N);

  // print(B);

  ll ans = B[0][0];
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}
0