結果

問題 No.1595 The Final Digit
コンテスト
ユーザー h2929
提出日時 2021-07-09 21:47:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,475 bytes
コンパイル時間 4,009 ms
コンパイル使用メモリ 235,432 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 15:50:19
合計ジャッジ時間 4,746 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
#define ll long long int
#define INF 1000000000000000000
using namespace atcoder;
using namespace std;
template<typename T>
struct matrix {
  public:
    matrix() {}
    matrix(int n, int m) : mat(n, std::vector<T>(m, 0)) {}
    matrix(int n) : mat(n, std::vector<T>(n, 0)) {}

  int height() const {
    return mat.size();
  }
  int width() const {
    return mat[0].size();
  }
  inline const std::vector<T> &operator[](int k) const {
    return (mat.at(k));
  }

  inline std::vector<T> &operator[](int k) {
    return (mat.at(k));
  }
  static matrix I(size_t n) {
    matrix mat(n);
    for (int i = 0; i < n; i++) 
      mat[i][i] = 1;
    return (mat);
  }
  matrix &operator+=(const matrix b) {
    int n = height(), m = width();
    assert(n == b.height() && m == b.width());
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        (*this)[i][j] += b[i][j];
    return (*this);
  }
  matrix &operator-=(const matrix b) {
    int n = height(), m = width();
    assert(n == b.height() && m == b.width());
    for(int i = 0; i < n; i++)
      for(int j = 0; j < m; j++)
        (*this)[i][j] -= b[i][j];
    return (*this);
  }
  matrix &operator*=(const matrix b) {
    int n = height(), m = width(), p = b.width();
    assert(m == b.height());
    std::vector< std::vector< T > > c(n, std::vector< T >(p, 0));
    for(int i = 0; i < n; i++)
      for(int j = 0; j < p; j++)
        for(int k = 0; k < m; k++)
          c[i][j] = (c[i][j] + (*this)[i][k] * b[k][j]);

    mat.swap(c);
    return (*this);
  }

 
  matrix &operator^=(long long int k) {
    matrix b = matrix::I(height());
    while(k > 0) {
      if(k & 1) b *= *this;
      *this *= *this;
      k >>= 1LL;
    }
    mat.swap(b.mat);
    return (*this);
  }
  matrix operator+(const matrix b) const {
    return (matrix(*this) += b);
  }
  matrix operator*(const matrix b) const {
    return (matrix(*this) *= b);
  }
  matrix operator-(const matrix b) const {
    return (matrix(*this) -= b);
  }
  matrix operator^(const long long int k) const {
    return (matrix(*this) ^= k);
  }
  friend std::ostream &operator<<(std::ostream &os, matrix p) {
    int n = p.height();
    int m = p.width();
    for(int i = 0; i < n; i++) {
      os << "[";
      for(int j = 0; j < m; j++) {
        os << p[i][j] << (j + 1 == m ? "]\n" : ",");
      }
    }
    return (os);
  }
  T determinant() {
    matrix b(*this);
    assert(width() == height());
    T ret = 1;
    for(int i = 0; i < width(); i++) {
      int idx = -1;
      for(int j = i; j < width(); j++) {
        if(b[j][i] != 0) idx = j;
      }
      if(idx == -1) return (0);
      if(i != idx) {
        ret *= -1;
        swap(b[i], b[idx]);
      }
      ret *= b[i][i];
      T vv = b[i][i];
      for(int j = 0; j < width(); j++) {
        b[i][j] /= vv;
      }
      for(int j = i + 1; j < width(); j++) {
        T a = b[j][i];
        for(int k = 0; k < width(); k++) {
          b[j][k] -= b[i][k] * a;
        }
      }
    }
    return (ret);
  }
    
  private:
    std::vector<std::vector<T>> mat;
};

using mint = modint;

int main(void){
  mint::set_mod(10);
  ll p, q, r, k;
  cin >> p >> q >> r >> k;

  matrix<mint> mat(3);
  mat[0][0] = 1;
  mat[0][1] = 1;
  mat[0][2] = 1;
  mat[1][0] = 1;
  mat[2][1] = 1;
  mat ^= (k-3);
  matrix<mint> v(3, 1);
  v[0][0] = r; 
  v[1][0] = q; 
  v[2][0] = p; 
  mat *= v;
  cout << mat[0][0].val() << endl;
  

  return 0;
}
0