結果
問題 | No.534 フィボナッチフィボナッチ数 |
ユーザー | mai |
提出日時 | 2017-06-23 23:31:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,783 bytes |
コンパイル時間 | 3,286 ms |
コンパイル使用メモリ | 215,404 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-03 03:44:43 |
合計ジャッジ時間 | 4,150 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 1 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 2 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
ソースコード
#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" // define macro "/D__MAI" using namespace std; typedef long long int ll; #define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl; #define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;} #define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl; #define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;} #define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;} #define ALL(v) (v).begin(),(v).end() #define repeat(l) for(auto cnt=0;cnt<(l);++cnt) #define iterate(b,e) for(auto cnt=(b);cnt!=(e);++cnt) #define MD 1000000007ll #define PI 3.1415926535897932384626433832795 template<typename T1, typename T2> ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; } #define TIME chrono::system_clock::now() #define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count()) namespace { std::chrono::system_clock::time_point ttt; void tic() { ttt = TIME; } void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - ttt)); } std::chrono::system_clock::time_point tle = TIME; #ifdef __MAI void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); } #else #define safe_tle(k) ; #endif } template<typename T> //typedef double T; class matrix { public: size_t height, width; valarray<T> data; matrix(size_t height, size_t width) :height(height), width(width), data(height*width) {} matrix(size_t height, size_t width, const valarray<T>& data) :height(height), width(width), data(height*width, data) {} inline T& operator()(size_t y, size_t x) { return data[y*width + x]; } inline T operator() (size_t y, size_t x) const { return data[y*width + x]; } inline T& at(size_t y, size_t x) { return data[y*width + x]; } inline T at(size_t y, size_t x) const { return data[y*width + x]; } inline void resize(size_t h, size_t w) { height = h; width = w; data.resize(h*w); } inline void fill(T val) { data = val; } matrix<T>& setDiag(T val) { for (size_t i = 0, en = min(width, height); i < en; ++i)at(i, i) = val; return *this; } inline bool issquare() { return height == width; } void print(ostream& os) { os << "- - -" << endl; // << setprecision(3) for (size_t y = 0; y < height; ++y) { for (size_t x = 0; x < width; ++x) { os << setw(7) << at(y, x) << ' '; }os << endl; } } template<typename MT> void copyto2d(MT& d2) { for (size_t i = 0; i < width*height; ++i) { d2[i / width][i%width] = data[i]; } } // mathematics void pow(long long) const; double det() const; T tr(); matrix<T>& transpose_self(); matrix<T> transpose() const; }; // IO template<typename T> inline ostream& operator << (ostream& os, matrix<T> mat) { mat.print(os); return os; } // スカラー template<typename T> inline matrix<T>& operator+=(matrix<T>& mat, T val) { mat.data += val; return mat; } template<typename T> inline matrix<T>& operator*=(matrix<T>& mat, T val) { mat.data *= val; return mat; } template<typename T> inline matrix<T>& operator/=(matrix<T>& mat, T val) { mat.data /= val; return mat; } template<typename T> inline matrix<T>& operator^=(matrix<T>& mat, T val) { mat.data ^= val; return mat; } // 行列 template<typename T> inline matrix<T>& operator+=(matrix<T>& mat1, matrix<T>& mat2) { mat1.data += mat2.data; return mat1; } template<typename T> inline matrix<T> operator+(matrix<T>& mat1, matrix<T>& mat2) { return matrix<T>(mat1.height, mat1.width, mat1.data + mat2.data); } // 掛け算 template<typename T> matrix<T> multiply(const matrix<T>& mat1, const matrix<T>& mat2) { assert(mat1.width == mat2.height); matrix<T> result(mat1.height, mat2.width); for (size_t i = 0, j, k; i < mat1.height; i++) { for (j = 0; j < mat2.width; j++) { for (k = 0; k < mat1.width; k++) { result(i, j) += mat1(i, k) * mat2(k, j); } } } return result; } template<typename T> valarray<T> multiply(const matrix<T>& mat1, const valarray<T>& vec2) { assert(mat1.width == vec2.size()); valarray<T> result(mat1.height); for (size_t i = 0, j; i < mat1.height; i++) { for (j = 0; j < mat1.width; j++) { result[i] += mat1(i, j) * vec2[j]; } } return result; } template<typename T> inline matrix<T>& operator*=(matrix<T>& mat1, matrix<T>& mat2) { mat1 = multiply(mat1, mat2); return mat1; } template<typename T> inline matrix<T> operator*(matrix<T>& mat1, matrix<T>& mat2) { return multiply(mat1, mat2); } void mojang(matrix<ll>& mat) { for (ll& d : mat.data) { d = d%MD; } } ll fibo(ll nn) { ll n = nn-1; matrix<ll> mat1(2, 2); mat1(0, 0) = 1; mat1(0, 1) = 1; mat1(1, 0) = 1; mat1(1, 1) = 0; matrix<ll> matz(2, 2); matz(0, 0) = 1; matz(1, 1) = 1; while (0<n) { if (n % 2 == 1) { matz = (matz*mat1); mojang(matz); } mat1 = (mat1*mat1); mojang(mat1); n /= 2; } matrix<ll> vect(2, 1); vect(0, 0) = 1; vect(1, 0) = 1; matrix<ll> rslt = matz * vect; return rslt(1, 0) % MD; } int main() { ll n; cin >> n; if (n==0){ cout << 0 << endl; return 0; } cout << fibo(fibo(n)) << endl; // cin >> n; // // cout << fibo(n) << endl; return 0; }