結果

問題 No.718 行列のできるフィボナッチ数列道場 (1)
コンテスト
ユーザー とばり
提出日時 2018-09-06 06:56:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,616 bytes
コンパイル時間 1,506 ms
コンパイル使用メモリ 175,456 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-17 14:19:34
合計ジャッジ時間 2,455 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using int64 = long long;
using uint64 = unsigned long long;

const int64 MOD = 1e9 + 7;

template <typename T>
struct Matrix
{
    vector<vector<T>> elt;

    Matrix(int m, int n) : elt(m, vector<T>(n)) {}
    Matrix(int n) : elt(n, vector<T>(n)) {}

    int row() const { return elt.size(); }
    int col() const { return elt.at(0).size(); }

    // [TODO]
    // +の実装
    // -の実装
    // +=, -=などの実装
    // 便利なコンストラクタの実装
    // 出力用文字列を生成する関数の実装
    // 参考: https://qiita.com/rinse_/items/9d87d5cb0dc1e89d005e

    // 各要素の値は法をmodとした乗算の結果となる
    Matrix operator*(const Matrix& mat)
    {
        Matrix res(row(), mat.col());
        for (int i = 0; i < row(); i++)
        {
            for (int j = 0; j < mat.col(); j++)
            {
                res[i][j] = 0;
                for (int k = 0; k < col(); k++)
                {
                    (res[i][j] += (*this)[i][k] * mat[k][j]) %= MOD;
                }
            }
        }
        return res;
    }

    const vector<T>& operator[](const int i) const
    {
        return elt.at(i);
    }

    vector<T>& operator[](const int i)
    {
        return elt.at(i);
    }

    Matrix identity()
    {
        Matrix res(row());
        for (int i = 0; i < row(); i++)
        {
            res[i][i] = 1;
        }
        return res;
    }

    Matrix pow(int64 n)
    {
        Matrix res = identity(),
               p = *this;
        while (n > 0)
        {
            if (n & 1)
            {
                res = res * p;
            }
            p = p * p;
            n >>= 1;
        }
        return res;
    }

    friend ostream& operator<<(ostream& os, Matrix m)
    {
        for (int i = 0; i < m.row(); i++)
        {
            os << "[";
            for (int j = 0; j < m.col(); j++)
            {
                if (j > 0) os << ", ";
                os << m.elt[i][j];
            }
            os << "]\n";
        }
        return os;
    }
};

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int64 N;
    cin >> N;

    Matrix<int64> A(4);
    A[0][0] = 1; A[0][1] = 1; A[0][2] = 1; A[0][3] = 2;
    A[1][0] = 0; A[1][1] = 1; A[1][2] = 1; A[1][3] = 2;
    A[2][0] = 0; A[2][1] = 1; A[2][2] = 0; A[2][3] = 0;
    A[3][0] = 0; A[3][1] = 1; A[3][2] = 0; A[3][3] = 1;

    Matrix<int64> x(4, 1);
    x[0][0] = 1; x[1][0] = 1; x[2][0] = 0; x[3][0] = 0;

    auto b = A.pow(N - 1) * x;

    cout << b[0][0] << endl;

    return 0;
}
0