結果

問題 No.1073 無限すごろく
ユーザー yukudoyukudo
提出日時 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 #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0