rt,求问矩阵快速幂如何减小常数?以下面这份代码为例:
typedef long long ll;
class Matrix {
public:
std::vector<std::vector<ll>> data;
int n;
Matrix() : n(0) { data.clear(); }
Matrix(int z) : n(z) { data.resize(n, std::vector<ll>(n, 0)); }
ll& at(int row, int col) {
return data[row - 1][col - 1];
}
ll& _at(int row, int col) { return data[row][col]; }
Matrix operator*(Matrix& B) const {
Matrix C(n);
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < n; ++k)
C._at(i, j) = (C._at(i, j) + (data[i][k] * B._at(k, j)) % mod) % mod;
return C;
}
void print() const {
for (const auto& row : data) {
for (const auto& elem : row) {
std::cout << elem << " ";
}
std::cout << std::endl;
}
}
} in, op, op2;
Matrix power(Matrix z, ll exp) {
Matrix ret(z.n), base = z;
for (int i = 0; i < z.n; ++i)
ret._at(i, i) = 1;
for (; exp; exp >>= 1)
(exp & 1) && (ret = ret * base, 0),
base = base * base;
return ret;
}