結果

問題 No.1595 The Final Digit
コンテスト
ユーザー tonakai
提出日時 2021-07-10 00:30:18
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,131 bytes
コンパイル時間 2,520 ms
コンパイル使用メモリ 204,620 KB
最終ジャッジ日時 2025-01-22 23:11:34
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define endl "\n"              //←これ
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ll> pdl;
typedef pair<ll,ld> pld;
typedef pair<ld,ld> pdd;
#define rep(i,n) for(ll i=0; i<(ll)(n); i++)
#define repo(i,n) for(ll i=1; i<(ll)(n); i++)
#define pb push_back
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define lb(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define ub(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define cou(x) __builtin_popcountll(x)
const ld pi=acos(-1.0);
const ll INF = 1LL<<61;
template<class T>bool chmax(T &a, const T &b) { 
  if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) {
  if (b<a) { a=b; return 1; } return 0; }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

vector<ll> vl(ll n,ll x){
  vector<ll> re(n,x);
  return re;}
vector<vector<ll>> vl(ll n, ll m,ll x){
  vector<vector<ll>> re(n,vector<ll>(m,x));
  return re;}
vector<vector<vector<ll>>> vl(ll n, ll m, ll l,ll x){
  vector<vector<vector<ll>>> re(n,vector<vector<ll>>(m,vector<ll>(l,x)));
  return re;}

template<class T>void out(T x) {cout << x << endl;}
template<class T>void out(T x,T y) {cout << x << " " << y << endl;}
template<class T>void out(T x,T y,T z) {cout << x << " " << y << " " << z << endl;}
template<class T>void out(T x,T y,T z,T a) {cout << x << " " << y << " " << z << " " << a << endl;}
template<class T>void out(pair<T,T> p) {cout << p.fi << " " << p.se << endl;}

template<class T>void vout(vector<T> &v) {
  if(v.size() > 0) { for(auto it = v.begin(); it < v.end(); it++) {
	  cout << *it;
	  if(it != v.end() - 1) cout << " ";
  } } cout << endl; }

template<class T>void vout(vector<vector<T>> &v) {
  if(v.size() > 0) { for(auto it = v.begin(); it < v.end(); it++) {
  vout(*it); } }
}

template<class T>void vout(vector<pair<T,T>> &v) {
  if(v.size() > 0) { for(auto it = v.begin(); it < v.end(); it++) {
  out(*it); } }
}


//——————————————————matrix　行列———————————————————————————

template< class T >
struct mat {
    std::vector< std::vector< T > > A;
    mat() {}
    mat(size_t n, size_t m) : A(n, std::vector< T >(m, 0)) {}
    mat(size_t n) : A(n, std::vector< T >(n, 0)) {};
    size_t height() const {
        return (A.size());
    }
    size_t width() const {
        return (A[0].size());
    }
    inline const std::vector< T > &operator[](ll k) const {
        return (A.at(k));
    }
    inline std::vector< T > &operator[](ll k) {
        return (A.at(k));
    }
    static mat I(size_t n) {
        mat ma(n);
        rep(i,n) ma[i][i] = 1;
        return (ma);
    }
    mat &operator*=(const mat &B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        std::vector< std::vector< T > > C(n, std::vector< T >(m, 0));
        rep(i,n)
            rep(j,m)
                rep(k,p)
                    C[i][j] = ((C[i][j] + (*this)[i][k] * B[k][j])%10+10)%10;
        A.swap(C);
        return (*this);
    }
    mat operator*(const mat &B) const {
        return (mat(*this) *= B);
    }
    
    mat pow(int64_t k) const {
        auto res = I(A.size());
        auto M = *this;
        while (k > 0) {
            if (k & 1) {
                res *= M;
            }
            M *= M;
            k >>= 1;
        }
        return res;
    }
};

template<class T> void vout(mat<T> ma) {
  rep(i,ma.height()) vout(ma[i]);
}

//—————————————————————————————————————————————————




int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision (15);


  ll a,b,c,d;
  cin>>a>>b>>c>>d;

  mat<ll> ma(3,3);
  ma[0]={1,1,1};
  ma[1]={1,0,0};
  ma[2]={0,1,0};

  ma=ma.pow(d-3);

  mat<ll> st(3,1);
  st[0][0]=c%10;
  st[1][0]=b%10;
  st[2][0]=a%10;

  st=ma*st;

  out(st[0][0]);
}
0