适合竞赛用，应该是相关模板最简洁的之一吧，不需要的部分（参数传递、命名空间、类型别名什么的）自己根据实际情况改一改就可以了。 ```cpp namespace MTX { using i64 = int64_t; constexpr i64 MTX_SIZE = 3; using vec = std::array; using mtx = std::array; 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 ``` 使用样例（斐波那契数列）： ```cpp #include namespace MTX { using i64 = int64_t; constexpr i64 MTX_SIZE = 3; using vec = std::array; using mtx = std::array; 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; } ```

back to basic frontend day21