C++: 2次元行列クラスの作成
とりあえず、行列の積(operator*)と累乗(pow)のみ実装。
全ての値はMの剰余としているが、適宜変更して使用する。
template <typename T>
class Matrix {
public:
Matrix(int row, int column, T value=T()) {
data.resize(row, std::vector<T>(column, value));
}
int rows() const { return static_cast<int>(data.size()); }
int columns() const { return static_cast<int>(data[0].size()); }
Matrix<T> operator*(Matrix<T> const& rhs) const {
int m = rows();
int n = rhs.rows();
int p = rhs.columns();
Matrix<T> ret(m, p);
for (int i=0; i < m; ++i) {
for (int j=0; j < p; ++j) {
for (int k=0; k < n; ++k) {
ret[i][j] = (ret[i][j] + data[i][k] * rhs[k][j]) % M;
}
}
}
return ret;
}
std::vector<T> const& operator[](size_t n) const { return data[n]; }
std::vector<T> & operator[](size_t n) { return data[n]; }
std::vector<std::vector<T> > data;
private:
static int const M = 10007;
};
template <typename T>
Matrix<T> pow(Matrix<T> mat, long long int n) {
int m = mat.rows();
Matrix<T> ret(m, m);
for (int i=0; i < m; ++i) ret[i][i] = 1; // identity matrix
while (n > 0) {
if (n & 1) ret = ret * mat;
mat = mat * mat;
n >>= 1;
}
return ret;
}
