結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
ユーザー 01 159 Romy01 159 Romy
提出日時 2024-11-29 11:42:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,118 bytes
コンパイル時間 2,380 ms
コンパイル使用メモリ 204,188 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-29 11:42:44
合計ジャッジ時間 3,537 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 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 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 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 AC 2 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = a; i > (b); --i)
#define ar array
#define sz(x) (int) (x).size()
#define pii pair<int,int>
#define fi first
#define se second
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef pair<double,int> pdi;
typedef vector<int> vi;
#define all(x) (x).begin(), (x).end()

template<typename T>
void min_self(T& A, T B) {
    A = min(A,B);
}
template<typename T>
void max_self(T& A, T B) {
    A = max(A,B);
}

const int mxn=1e5;
ll n;

const ll mod = 1e9+7; // faster if const
template<class T, int N> struct Matrix {
    typedef Matrix M;
    array<array<T, N>, N> d{};
    M operator*(const M& m) const {
        M a;
        rep(i,0,N) rep(j,0,N)
            rep(k,0,N) a.d[i][j] = (a.d[i][j] + d[i][k]*m.d[k][j]%mod)%mod;
        return a;
    }
    vector<T> operator*(const vector<T>& vec) const {
        vector<T> ret(N);
        rep(i,0,N) rep(j,0,N) ret[i] = (ret[i] + d[i][j] * vec[j]%mod)%mod;
        return ret;
    }
    M operator^(ll p) const {
        assert(p >= 0);
        M a, b(*this);
        rep(i,0,N) a.d[i][i] = 1;
        while (p) {
            if (p&1) a = a*b;
            b = b*b;
            p >>= 1;
        }
        return a;
    }
};

void solve() {
    // vector<ll> fibo(10);
    // fibo[0] = 0, fibo[1] = 1;
    // rep(i,2,10) {
    //     fibo[i] = fibo[i-1]+fibo[i-2];
    // }
    // vector<ll> seq(10);
    // ll pr = 0;
    // rep(i,0,10) {
    //     pr = (pr + fibo[i]*fibo[i])%mod;
    //     seq[i] = pr;
    //     cout <<seq[i] <<endl;
    // }
    // auto linrec = berlekampMassey(seq);
    // rep(i,0,sz(linrec)) {
    //     cout <<linrec[i] <<",";
    // }
    cin >>n;
    ll n1 = mod-1;
    Matrix<ll,3> mat;
    mat.d = {{ {{2,2,n1}},{{1,0,0}} ,{{0,1,0}} }};
    vector<ll> v = {2,1,0};
    if(n<3) {
        cout <<v[2-n] <<"\n";
        return;
    }
    v = (mat^(n-2)) * v;
    cout <<v[0] <<"\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}
0