6 months ago

分享一下自己常用的矩阵快速幂优化dp模板

适合竞赛用，应该是相关模板最简洁的之一吧，不需要的部分（参数传递、命名空间、类型别名什么的）自己根据实际情况改一改就可以了。

namespace MTX {
using i64 = int64_t;
constexpr i64 MTX_SIZE = 3;
using vec = std::array<i64, MTX_SIZE>;
using mtx = std::array<vec, MTX_SIZE>;

mtx &mul(mtx &a, const mtx &b, const i64 m = INT64_MAX) {
    mtx r{};
    for (int i = 0; i < MTX_SIZE; ++i)
        for (int j = 0; j < MTX_SIZE; ++j)
            for (int k = 0; k < MTX_SIZE; ++k)
                r[i][j] = (r[i][j] + a[i][k] * b[k][j] % m) % m;
    a = std::move(r);
    return a;
}

mtx &dp(mtx &s, mtx& f, i64 n, const i64 m = INT64_MAX) {
    while (n) {
        if (n & 1) mul(s, f, m);
        n >>= 1, mul(f, f, m);
    }
    return s;
}
} // namespace MTX

使用样例（斐波那契数列）：

#include <bits/stdc++.h>

namespace MTX {
using i64 = int64_t;
constexpr i64 MTX_SIZE = 3;
using vec = std::array<i64, MTX_SIZE>;
using mtx = std::array<vec, MTX_SIZE>;

mtx &mul(mtx &a, const mtx &b, const i64 m = INT64_MAX) {
    mtx r{};
    for (int i = 0; i < MTX_SIZE; ++i)
        for (int j = 0; j < MTX_SIZE; ++j)
            for (int k = 0; k < MTX_SIZE; ++k)
                r[i][j] = (r[i][j] + a[i][k] * b[k][j] % m) % m;
    a = std::move(r);
    return a;
}

mtx &dp(mtx &s, mtx& f, i64 n, const i64 m = INT64_MAX) {
    while (n) {
        if (n & 1) mul(s, f, m);
        n >>= 1, mul(f, f, m);
    }
    return s;
}
} // namespace MTX

int main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(nullptr);
    MTX::mtx s{(MTX::vec)
        {1, 1},
        {0, 0}
    }, f{(MTX::vec)
        {0, 1},
        {1, 1}
    };
    MTX::i64 n;
    std::cin >> n;
    std::cout << MTX::dp(s, f, n - 1, 1e9 + 7)[0][0] << std::endl;
    return 0;
}

pow·matrix·c++

119 views