yukicoder No.659 - 徘徊迷路

問題

初めて行列演算が腑に落ちた気がする。

行列演算を使うことで、ベクトルの各成分の入れ替えたり、ついでに成分の値を倍にしたりできる。この問題だと、位置を64要素を持つベクトルと見て、移動を64x64行列の演算と見なせる。

今回の問題の自然な解き方の流れとしては、

1. DPを定義する
2. T = 10^8なので間に合わない。どうしよう
3. 何回目かに限らず、遷移は完全に一致することに気付く
4. dp配列をベクトルと、遷移を行列演算と見なせる
5. 行列を定義する

みたいな感じだと思う。つまり、行列累乗はDPの延長上にある。

遷移が完全に一致しているような問題に次出会ったら行列累乗を使える気がする。

一応自作のMatrix構造体の実装を貼っておく。

#define rep(i, n) for (int i = 0; i < int(n); i++)
using i64 = long long;
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }

template <typename T>
struct Matrix {
  vector<vector<T>> v;
  int r, c;
  Matrix(int r, int c, T d) : r(r), c(c) {
    v = vector<vector<T>>(r, vector<T>(c, d));
  }
  Matrix(vector<vector<T>> v) : v(v) {
    r = v.size();
    c = v[0].size();
  }
  vector<T>& operator[](int x) {
    return v[x];
  }
  Matrix<T> operator*=(Matrix<T> that) {
    assert(c == that.r);
    auto ret = Matrix<T>(r, that.c, 0);
    rep(i, r) rep(j, that.c) rep(k, c) {
      ret[i][j] += v[i][k] * that[k][j];
    }
    return *this = ret;
  }
  Matrix<T> operator*(Matrix<T> that) {
    return *this *= that;
  }
  Matrix<T> pow(i64 n) {
    assert(r == c);
    auto e = Matrix<T>(r, c, 0);
    rep(i, r) e[i][i] = 1;
    return exp(*this, n, e);
  }
};