#275280 (C++11) No.720 行列のできるフィボナッチ数列道場 (2)

提出ソース

結果

問題	No.720 行列のできるフィボナッチ数列道場 (2)
ユーザー	ミドリムシ
提出日時	2018-07-27 23:34:27
言語	C++11 (gcc 11.4.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	3 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	2 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
    
}

yukicoder

結果

テストケース

ソースコード