結果

問題 No.534 フィボナッチフィボナッチ数
ユーザー NishionyamaNishionyama
提出日時 2019-10-18 17:55:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 7,388 bytes
コンパイル時間 1,630 ms
コンパイル使用メモリ 174,980 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-07 20:59:17
合計ジャッジ時間 3,201 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 2 ms
4,376 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 2 ms
4,384 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 2 ms
4,380 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 1 ms
4,376 KB
testcase_30 AC 1 ms
4,380 KB
testcase_31 AC 1 ms
4,380 KB
testcase_32 AC 1 ms
4,376 KB
testcase_33 AC 2 ms
4,376 KB
testcase_34 AC 2 ms
4,376 KB
testcase_35 AC 2 ms
4,380 KB
testcase_36 AC 2 ms
4,376 KB
testcase_37 AC 2 ms
4,380 KB
testcase_38 AC 2 ms
4,380 KB
testcase_39 AC 2 ms
4,376 KB
testcase_40 AC 1 ms
4,376 KB
testcase_41 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

long long int mod = 1000000007;

// PowMod( base, index, modulo) return base ** index % modulo {{{
// PowMod = base ** index % mod ( natural numbers )
inline long long int PowMod( long long int base, long long int index, long long int modulo = mod ){
    if( index == 0 ) return 1;
    // O( log(index) )
    if( index % 2 ){
        return base * PowMod(base, index - 1, modulo) % modulo;
    }else{
        long long int Phalf = index / 2;
        long long int half = PowMod(base, Phalf, modulo);
        return half * half % modulo;
    }
}
// }}}
// CombMod( n, r, modulo ) return nCr % modulo {{{
// CombMod(ination) = nCr % mod ( natural number )
inline long long int CombMod( long long int n, long long int r, long long int modulo = mod){
    if( n < r ) return CombMod(r,n,modulo);
    long long int Upper = 1;
    long long int Lower = 1;
    for(long long int i = 0; i < r; i++){
        Upper = Upper * (n-i) % modulo;
        Lower = Lower * (i+1) % modulo;
    }
    // Return (Upper / Lower)
    long long int ret = Upper * PowMod(Lower,modulo-2,modulo) % modulo;
    return ret;
}
// }}}
// FactMod( n, modulo ) return n! % modulo {{{
// Fact(orial) = n! % mod ( natural number )
inline long long int Fact( long long int n, long long int modulo = mod){
    long long int Upper = 1;
    for(long long int i = 0; i < n; i++){
        Upper = Upper * (n-i) % modulo;
    }
    return Upper;
}
// }}}
// modint {{{

struct modint{
    long long int a;
    inline modint( long long int x = 0 ) noexcept : a(x % mod) {}
    inline long long int &value() noexcept { return a; }
    inline const long long int &value() const noexcept { return a; }
    inline modint operator+(const modint rhs) const noexcept{ return modint(*this) += rhs; }
    inline modint operator+(const int rhs) const noexcept{ return modint(*this) += rhs; }
    inline modint operator+(const long long int rhs) const noexcept{ return modint(*this) += rhs; }
    inline modint operator-(const modint rhs) const noexcept{ return modint(*this) -= rhs; }
    inline modint operator-(const int rhs) const noexcept{ return modint(*this) -= rhs; }
    inline modint operator-(const long long int rhs) const noexcept{ return modint(*this) -= rhs; }
    inline modint operator*(const modint rhs) const noexcept{ return modint(*this) *= rhs; }
    inline modint operator*(const int rhs) const noexcept{ return modint(*this) *= rhs; }
    inline modint operator*(const long long int rhs) const noexcept{ return modint(*this) *= rhs; }
    inline modint operator/(const modint rhs) const noexcept{ return modint(*this) /= rhs; }
    inline modint operator/(const int rhs) const noexcept{ return modint(*this) /= rhs; }
    inline modint operator/(const long long int rhs) const noexcept{ return modint(*this) /= rhs; }
    inline modint operator+=(const modint rhs) noexcept{ a += rhs.a; if( a >= mod ) a -= mod; return*this; }
    inline modint operator-=(const modint rhs) noexcept{ a -= rhs.a; if( a < 0 ) a += mod; return *this; }
    inline modint operator*=(const modint rhs) noexcept{ a = a * rhs.a % mod ;  return *this; }
    inline modint operator/=(const modint rhs) noexcept{ a = a * PowMod(rhs.a,mod-2) % mod; return *this; }
};

// }}}

// Matrix Definition{{{

template< class T >
struct Matrix{
    vector< vector<T> > A;

    Matrix(){};
    Matrix( int n, int m ) {
        A.assign(n,vector<T>(m,0));
    };
    Matrix( int n ) {
        A.assign(n,vector<T>(n,0));
    };

    int height() const {
        return (A.size());
    }

    int width() const {
        return (A[0].size());
    }

    inline vector<T> &operator[]( int k ) {
        return (A.at(k));
    }

    inline const vector<T> &operator[]( int k ) const {
        return (A.at(k));
    }

    // 単位行列
    static Matrix E( int n ){
        Matrix mat(n);
        for( int i = 0; i < n; i++ ) mat[i][i] = 1;
        return mat;
    }

    Matrix &operator+=( const Matrix &B ){
        int 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 ){
        int 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 ){
        int 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] += (*this)[i][k] * B[k][j];
        A.swap(C);
        return (*this);
    }

    Matrix power( ll k ){
        Matrix B = Matrix::E(height());
        while( k > 0 ){
            if( k&1 ) B *= *this;
            *this *= *this;
            k >>= 1;
        }
        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 );
    }

    void Print(){
        int n = height(), m = width();
        for( int i = 0; i < n; i++ ){
            printf ("[");
            for( int j = 0; j < m; j++ ){
                printf ("%lld%s", (*this)[i][j], j == m-1 ? "]\n" : "," );
            }
        }
    }

};

// }}}

int main() {

    ll mod1 = 1000000007;
    ll mod2 = 2000000016ll;

    ll N;
    Scll(N);

    Matrix<modint> fi(2,2);
    Matrix<modint> c(1,2);
    c[0][0] = 1; c[0][1] = 0;
    fi[0][0] = 1;
    fi[0][1] = 1;
    fi[1][0] = 1;
    fi[1][1] = 0;

    mod = mod2;
    fi.power(N);
    c *= fi;

    ll fibn = c[0][1].a;
    // printf ("%lld\n", fibn );

    mod = mod1;
    c[0][0] = 1; c[0][1] = 0;
    fi[0][0] = 1;
    fi[0][1] = 1;
    fi[1][0] = 1;
    fi[1][1] = 0;
    fi.power(fibn);
    c *= fi;

    modint ans = c[0][1];

    printf ("%lld\n", ans );

    return 0;

}
0