C++ – 矩阵幂加速 DP

络谷 P1962 斐波那契数列

#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#pragma warning(disable:4996)
using namespace std;

const int maxn = 3;
const long long mod = 1e9 + 7;

struct mat_t {
    int n, m;
    long long mat[maxn][maxn];

    mat_t() { memset(mat, 0, sizeof mat); }

    void unit() {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                mat[i][j] = i == j;
    }

    friend mat_t operator *(const mat_t& a, const mat_t& b) {
        mat_t res;
        res.n = a.n;
        res.m = b.m;
        for (int i = 1; i <= res.n; ++i)
            for (int j = 1; j <= res.m; ++j)
                for (int k = 1; k <= min(a.m, b.n); ++k)
                    res.mat[i][j] += a.mat[i][k] * b.mat[k][j], res.mat[i][j] %= mod;
        return res;
    }

    friend mat_t& operator *=(mat_t& a, const mat_t& b) {
        a = a * b;
        return a;
    }

    friend mat_t qpow(mat_t m, long long e) {
        mat_t res;
        res.n = m.n;
        res.m = m.m;
        res.unit();
        while (e) {
            if (e & 1) res *= m;
            m *= m;
            e >>= 1;
        }
        return res;
    }
};

int main() {
    long long n;
    mat_t s;
    s.n = 1;
    s.m = 2;
    s.mat[1][1] = 1;
    s.mat[1][2] = 1;
    mat_t m;
    m.n = 2;
    m.m = 2;
    m.mat[1][1] = 1; m.mat[1][2] = 1;
    m.mat[2][1] = 1; m.mat[2][2] = 0;
    scanf("%lld", &n);
    m = qpow(m, max(n - 2, 0ll));
    s *= m;
    printf("%lld\n", s.mat[1][1]);
    return 0;
}