結果

問題 No.1595 The Final Digit
ユーザー lynmisakuralynmisakura
提出日時 2021-07-09 21:40:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,753 bytes
コンパイル時間 2,395 ms
コンパイル使用メモリ 208,108 KB
最終ジャッジ日時 2025-01-22 21:14:54
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

// code by lynmisakura. wish to be accepted!
#include<bits/stdc++.h>
using namespace std;

#define REP(i,N) for(int i = 0;i < N;i++)
using ll = long long;

#include<atcoder/modint>
using mint = atcoder::modint;

namespace lyn{
  template <class T> struct Matrix{
    int R,C;
    std::vector<std::vector<T>> dat;
    // コンストラクタ
    Matrix(){}
    Matrix(int R,int C):R(R),C(C){
      dat.assign(R,std::vector<T>(C,0));
    }
    // 演算子オーバーロード
    Matrix& operator+=(const Matrix& a){
      assert(R == a.R && C == a.C);
      for(int i = 0;i < R;i++){
        for(int j = 0;j < C;j++){
          dat[i][j] += a.dat[i][j];
        }
      }
      return *this;
    }
    Matrix& operator-=(const Matrix& a){
      assert(R == a.R && C == a.C);
      for(int i = 0;i < R;i++){
        for(int j = 0;j < C;j++){
          dat[i][j] -= a.dat[i][j];
        }
      }
      return *this;
    }
    // 行列の積
    Matrix operator *(const Matrix& a){
      Matrix C(R,a.C);
      for(int i = 0;i < R;i++){
        for(int k = 0;k < a.R;k++){
          for(int j = 0;j < a.C;j++){
            C.dat[i][j] += (dat[i][k] * a.dat[k][j]);
          }
        }
      }
      return C;
    }
    // 行列の定数倍
    Matrix& operator *= (const T& a){
      for(int i = 0;i < R;i++){
        for(int j = 0;j < C;j++){
          dat[i][j] *= a;
        }
      }
    }
    Matrix& operator /= (const T& a){
      for(int i = 0;i < R;i++){
        for(int j = 0;j < C;j++){
          dat[i][j] /= a;
        }
      }
    }
    // 行列累乗
    Matrix pow(long long N){
      Matrix A(*this),B(R,C);
      for(int i=0;i<R;i++){
        B.dat[i][i] = 1;
      }
      while(N > 0){
        if(N & 1) B = B * A;
        A = A * A;
        N >>= 1;
      }
      return B;
    }
    // 参照
    std::vector<T>& operator[](int i){
      return dat[i];
    }
    Matrix& operator[](const Matrix& a){
      assert(R == a.R && C == a.C);
      for(int i = 0;i < R;i++){
        for(int j = 0;j < C;j++){
          dat[i][j] = a.dat[i][j];
        }
      }
      return *this;
    }
    // 出力
    void print(){
      for(int i = 0;i < R;i++){
        for(int j = 0;j < C;j++){
          std::cout << dat[i][j] << (j < C - 1 ? ' ' : '\n');
        }
      }
      std::cout << '\n';
    }
  };
}

int main(void){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  
  int p,q,r;
  ll k;
  cin >> p >> q >> r >> k;

  mint::set_mod(10);

  lyn::Matrix<mint> M(4,4);
  M[0] = {1,1,1,0};
  M[1] = {1,0,0,0};
  M[2] = {0,1,0,0};
  M[3] = {0,0,1,0};
  
  lyn::Matrix<mint> A = M.pow(k-3);

  mint ans = A[0][0] * mint(r) + A[0][1] * mint(q) + A[0][2] * mint(p);

  cout << ans.val() << '\n';

}
0