8.29.2011

C++: Matrix class

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 件のコメント:

コメントを投稿