結果
| 問題 | No.720 行列のできるフィボナッチ数列道場 (2) |
| ユーザー |
 ミドリムシ
|
| 提出日時 | 2018-07-27 23:34:27 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 6,302 bytes |
| コンパイル時間 | 830 ms |
| コンパイル使用メモリ | 71,524 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-07-05 05:32:15 |
| 合計ジャッジ時間 | 1,441 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 20 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>using namespace std;template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }template<class T> inline void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }template<class T> inline void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }template<class T> inline void First(T condition){ if(condition) cout << "First" << endl; else cout << "Second" << endl; }int character_count(string text, char character){ int ans = 0; for(int i = 0; i < text.size(); i++){ ans += (text[i] == character); } return ans; }long power(long base, long exponent, long module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){long root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}struct position{ int y, x; }; position move_pattern[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // double euclidean(position first, position second){return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); }template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++){ ans += to_string(*i) + " "; } ans.pop_back(); cout << ans << endl; }template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){return a / gcd(a, b) * b; }#define mod long(1e9 + 7)#define all(x) (x).begin(), (x).end()#define bitcount(n) __builtin_popcountl(long(n))#define fcout cout << fixed << setprecision(10)#define highest(x) (63 - __builtin_clzl(x))template< class T >struct Matrix{vector< vector< T > > A;Matrix() {}Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {}Matrix(size_t n) : A(n, vector< T >(n, 0)) {};Matrix(vector< vector< T > > x) : A(x) {};size_t height() const{return (A.size());}size_t width() const{return (A[0].size());}inline const vector< T > &operator[](int k) const{return (A.at(k));}inline vector< T > &operator[](int k){return (A.at(k));}static Matrix I(size_t n){Matrix mat(n);for(int i = 0; i < n; i++) mat[i][i] = 1;return (mat);}Matrix &operator+=(const Matrix &B){size_t n = height(), m = width();// assert(n == B.height() && m == B.width());for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)(*this)[i][j] = ((*this)[i][j] + B[i][j]) % mod;return (*this);}Matrix &operator-=(const Matrix &B){size_t n = height(), m = width();assert(n == B.height() && m == B.width());for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)(*this)[i][j] -= B[i][j];return (*this);}Matrix &operator*=(const Matrix &B){size_t n = height(), m = B.width(), p = width();// assert(p == B.height());vector< vector< T > > C(n, vector< T >(m, 0));for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)for(int k = 0; k < p; k++)C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]) % mod;A.swap(C);return (*this);}Matrix &operator^=(long long k){Matrix B = Matrix::I(height());while(k > 0) {if(k & 1) B *= *this;*this *= *this;k >>= 1LL;}A.swap(B.A);return (*this);}Matrix operator+(const Matrix &B) const{return (Matrix(*this) += B);}Matrix operator-(const Matrix &B) const{return (Matrix(*this) -= B);}Matrix operator*(const Matrix &B) const{return (Matrix(*this) *= B);}Matrix operator^(const long long k) const{return (Matrix(*this) ^= k);}friend ostream &operator<<(ostream &os, Matrix &p){size_t n = p.height(), m = p.width();for(int i = 0; i < n; i++) {os << "[";for(int j = 0; j < m; j++) {os << p[i][j] << (j + 1 == m ? "]\n" : ",");}}return (os);}T determinant(){Matrix B(*this);assert(width() == height());T ret = 1;for(int i = 0; i < width(); i++) {int idx = -1;for(int j = i; j < width(); j++) {if(B[j][i] != 0) idx = j;}if(idx == -1) return (0);if(i != idx) {ret *= -1;swap(B[i], B[idx]);}ret *= B[i][i];T vv = B[i][i];for(int j = 0; j < width(); j++) {B[i][j] /= vv;}for(int j = i + 1; j < width(); j++) {T a = B[j][i];for(int k = 0; k < width(); k++) {B[j][k] -= B[i][k] * a;}}}return (ret);}};Matrix<long> A, E;Matrix<long> power(long base){if(base % 2){return A * power(base - 1);}else if(base){Matrix<long> root_ans = power(base / 2);return root_ans * root_ans;}else{return E;}}int M;Matrix<long> fibonatti_sum(long base){if(base % 2){return fibonatti_sum(base - 1) + power(base * M);}else if(base){Matrix<long> root_ans = fibonatti_sum(base / 2);return root_ans + root_ans * power(base * M / 2);}else{return Matrix<long>(2, 2);}}int main(){long N;cin >> N >> M;A.A = {{1, 1}, {1, 0}};E.A = {{1, 0}, {0, 1}};cout << fibonatti_sum(N)[1][0] << endl;}