C++: 2次元行列クラスの作成
とりあえず、行列の積(operator*)と累乗(pow)のみ実装。
全ての値はMの剰余としているが、適宜変更して使用する。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | 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 件のコメント:
コメントを投稿