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; }
0 件のコメント:
コメントを投稿