結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cassert>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}

template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

const lli mod = 1000000007;

class matrix {
public:
    vector<vector<lli>> mat;
    int nsize, msize;
    matrix(int n, int m) {
        nsize = n;
        msize = m;
        mat.resize(nsize, vector<lli>(msize, 0));
    }
    matrix operator+(matrix m) {
        assert(nsize == m.nsize && msize == m.msize);
        matrix res(nsize, msize);
        REP(i, 0, nsize) {
            REP(j, 0, msize) {
                res.mat[i][j] = (mat[i][j] + m.mat[i][j]) % mod;
            }
        }
        return res;
    }
    matrix operator*(matrix m) {
        assert(msize == m.nsize);
        matrix res(nsize, m.msize);
        REP(i, 0, nsize) {
            REP(j, 0, m.msize) {
                REP(k, 0, msize) {
                    res.mat[i][j] = (res.mat[i][j] + (mat[i][k] * m.mat[k][j]) % mod) % mod;
                }
            }
        }
        return res;
    }
    static matrix init(int n) {
        matrix res(n, n);
        REP(i, 0, n) {
            res.mat[i][i] = 1;
        }
        return res;
    }
    void print() {
        cout << "---------------------------------" << endl;
        REP(i, 0, nsize) {
            REP(j, 0, msize) {
                cout << mat[i][j] << " ";
            }
            cout << endl;
        }
    }
};

matrix pow(matrix m, lli n) {
    if (n == 0) return matrix::init(m.nsize);
    if (n % 2 == 0) {
        matrix res = pow(m, n / 2);
        return (res * res);
    } else {
        return pow(m, n - 1) * m;
    }
}

int main() {
    lli N;
    cin >> N;
    const lli divS = 100000;
    const lli loop = N / divS;
    const lli rem = N % divS;

    matrix l(1, 2), r(2, 1), mid(2, 2), ini = matrix::init(2), fib(2, 2);
    l.mat[0][0] = r.mat[0][0] = mid.mat[1][1] = fib.mat[0][0] = fib.mat[0][1] = fib.mat[1][0] = 1;

    matrix res(2, 2), bs(2, 2), ans(2, 2);

    {
        matrix a = ini;
        REP(i, 0, divS) {
            a = a * fib;
            bs = bs + a * mid * a;
            if (i < rem) {
                res = res + a * mid * a;
            }
        }
    }

    {
        matrix a = pow(fib, divS);
        matrix t = matrix::init(2);
        REP(i, 0, loop) {
            ans = ans + t * bs * t;
            t = t * a;
        }
        ans = ans + t * res * t;
    }

    ans = l * ans * r;

    cout << ans.mat[0][0] << endl;

    return 0;
}
0