結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
コンテスト
ユーザー とばり
提出日時 2018-07-27 23:52:05
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,738 bytes
コンパイル時間 557 ms
コンパイル使用メモリ 67,596 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 06:11:21
合計ジャッジ時間 1,389 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using int64 = long long;

const int64 MOD = 1e9 + 7;

template <typename T>
struct Matrix {
    const int M;
    const int N;
    std::vector<std::vector<T>> elts;

    Matrix(int m, int n, T v = 0) : M(m), N(n), elts(M, std::vector<T>(N, v)) {}

    template <class InputIt>
    Matrix(int m, int n, InputIt first, InputIt last)
        : M(m), N(n), elts(M, std::vector<T>(N)) {
        for (int i = 0; i < M; i++) {
            std::copy(first + (i * n), first + ((i + 1) * n), elts[i].begin());
        }
    }

    const std::vector<T>& operator[](int m) const { return elts[m]; } 

    Matrix operator*(const Matrix& m) const {
        Matrix res(M, m.N, 0);
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < m.N; j++) {
                for (int k = 0; k < N; k++) {
                    (res.elts[i][j] += (elts[i][k] * m.elts[k][j]) % MOD) %= MOD;
                }
            }
        }
        return res;
    }

    Matrix identity() {
         Matrix m(N, N, 0);
         for (int i = 0; i < N; i++) m.elts[i][i] = 1;
         return m;
    }

    Matrix pow(int64 n) {
        if (n == 0) { return identity(); }
        else if (n % 2 == 1) { return *this * pow(n - 1); }
        else { Matrix m = pow(n / 2); return m * m; }
    }
};

int main() {
    int64 N;
    cin >> N;

    vector<int64> x{ 1, 0, 0, 1 },
                  A{ 1, 1, 2, 0,
                     1, 0, 0, 0,
                     1, 0, 1, 0,
                     1, 1, 2, 1 };
    Matrix<int64> xm(4, 1, x.begin(), x.end());
    Matrix<int64> Am(4, 4, A.begin(), A.end());

    auto bm = Am.pow(N - 1) * xm;
    cout << bm[3][0] << endl;

    return 0;
}
0