結果

問題 No.44 DPなすごろく
ユーザー not_522
提出日時 2015-07-19 10:00:50
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 4,764 bytes
コンパイル時間 1,764 ms
コンパイル使用メモリ 172,472 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-08 10:20:58
合計ジャッジ時間 2,263 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

namespace arithmetic {
  template<typename T> class Addition {
  public:
    template<typename V> T operator+(const V& v) const {
      T res(static_cast<const T&>(*this));
      return res += static_cast<T>(v);
    }
  };

  template<typename T> class Subtraction {
  public:
    template<typename V> T operator-(const V& v) const {
      T res(static_cast<const T&>(*this));
      return res -= static_cast<T>(v);
    }
  };

  template<typename T> class Multiplication {
  public:
    template<typename V> T operator*(const V& v) const {
      T res(static_cast<const T&>(*this));
      return res *= static_cast<T>(v);
    }
  };

  template<typename T> class Division {
  public:
    template<typename V> T operator/(const V& v) const {
      T res(static_cast<const T&>(*this));
      return res /= static_cast<T>(v);
    }
  };

  template<typename T> class Modulus {
  public:
    template<typename V> T operator%(const V& v) const {
      T res(static_cast<const T&>(*this));
      return res %= static_cast<T>(v);
    }
  };
}

template<typename T> class IndivisibleArithmetic : public arithmetic::Addition<T>, public arithmetic::Subtraction<T>, public arithmetic::Multiplication<T> {};

template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public arithmetic::Division<T> {};

template<typename T> class Vector : public arithmetic::Addition<Vector<T>>, public arithmetic::Subtraction<Vector<T>> {
protected:
  vector<T> val;

public:
  Vector(int n) : val(n, 0) {}

  T& operator[](int n) {
    return val[n];
  }
	
	Vector operator+=(const Vector& v) {
    for (int i = 0; i < size(); ++i) val[i] += v[i];
		return *this;
	}
	
	Vector operator-=(const Vector& v) {
    for (int i = 0; i < size(); ++i) val[i] -= v[i];
		return *this;
	}

  T operator*(const Vector& v) const {
    return inner_product(val.begin(), val.end(), const_cast<Vector&>(v).begin(), T(0));
  }

  int size() const {
    return val.size();
  }

  typename vector<T>::const_iterator begin() const {
    return val.begin();
  }

  typename vector<T>::const_iterator end() const {
    return val.end();
  }
};

template<typename T> class Matrix : public IndivisibleArithmetic<Matrix<T>> {
protected:
  vector<Vector<T>> val;
  
public:
  Matrix(int n, int m) : val(n, Vector<T>(m)) {}

  Vector<T>& operator[](int n) {
    return val[n];
  }
	
	Matrix operator+=(const Matrix& m) {
    for (int i = 0; i < (int)val.size(); ++i) val[i] += m[i];
		return *this;
	}
	
	Matrix operator-=(const Matrix& m) {
    for (int i = 0; i < (int)val.size(); ++i) val[i] -= m[i];
		return *this;
	}

  Matrix operator*=(const Matrix& _m) {
    Matrix &m = const_cast<Matrix&>(_m);
    Matrix res(size(), m[0].size());
    for (int i = 0; i < size(); ++i) {
      for (int j = 0; j < m.size(); ++j) {
        for (int k = 0; k < m[0].size(); ++k) {
          res[i][k] += val[i][j] * m[j][k]; 
        }
      }
    }
    return *this = res;
  }
  
  Vector<T> operator*(const Vector<T>& v) {
    Vector<T> res(size());
    for (int i = 0; i < size(); ++i) res[i] += val[i] * v;
    return res;
  }

  int size() const {
    return val.size();
  }
};

template<typename T> class SquareMatrix : public Matrix<T>, public arithmetic::Division<SquareMatrix<T>> {
public:
  SquareMatrix(int n) : Matrix<T>(n, n) {}

  SquareMatrix(const Matrix<T>& m) : Matrix<T>(m) {}

	SquareMatrix operator/=(const SquareMatrix& m) {
		return *this *= m.inverse();
	}

  SquareMatrix identity() const {
    SquareMatrix res(this->size());
    for (int i = 0; i < this->size(); ++i) res[i][i] = 1;
    return res;
  }

  SquareMatrix inverse() const {
    int n = this->size();
    SquareMatrix mat = *this;
    SquareMatrix inv = identity();
    for (int i = 0; i < n; ++i) {
      int p = i;
      for (int j = i + 1; j < n; ++j) {
        if (abs(mat[j][i]) > abs(mat[p][i])) p = j;
      }
      swap(mat[i], mat[p]);
      swap(inv[i], inv[p]);
      for (int j = i + 1; j < n; ++j) mat[i][j] /= mat[i][i];
      for (int j = 0; j < n; ++j) inv[i][j] /= mat[i][i];
      mat[i][i] = 1;
      for (int j = 0; j < n; ++j) {
        if (i == j) continue;
        T a = mat[j][i];
        for (int k = 0; k < n; ++k) {
          mat[j][k] -= a * mat[i][k];
          inv[j][k] -= a * inv[i][k];
        }
      }
    }
    return inv;
  }
};

template<typename T> T pow(T& m, long long n) {
  if (n == 0) {
    return m.identity();
  } else if (n < 0) {
    return m.identity() / pow(m, -n);
  }
  T mm = pow(m, n / 2);
  mm *= mm;
  if (n % 2) mm *= m;
  return mm;
}

int main() {
  SquareMatrix<long long> m(2);
  m[0][0] = m[0][1] = m[1][0] = 1;
  Vector<long long> v(2);
  v[0] = 1;
  int n;
  cin >> n;
  cout << (pow(m, n) * v)[0] << endl;
}
0