結果

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

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>
#include <cstddef>
#include <type_traits>
#include <vector>

using namespace std;
const long long int INF = numeric_limits<long long int>::max() / 4;
const int inf = numeric_limits<int>::max() / 4;
const long long int MOD1000000007 = 1000000007;
const long long int MOD998244353 = 998244353;
const double MATH_PI = 3.1415926535897932;

template<typename T1, typename T2>
inline void chmin(T1 &a, const T2 &b) { if (a > b) a = b; }

template<typename T1, typename T2>
inline void chmax(T1 &a, const T2 &b) { if (a < b) a = b; }

#define lint long long int
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define VI vector<int>
#define VLL vector<long long>
#define VC vector<char>
#define VB vector<bool>
#define PI pair<int, int>
#define PLL pair<long long, long long>
#define VPI vector<pair<int, int>>
#define VPLL vector<pair<long long, long long>>
#define VVI vector<vector<int>>
#define VVPI vecor<vector<pair<int, int>>>
#define VVPILL vector<vector<pair<int, long long>>>

#define SUM(v) accumulate(ALL(v), 0LL)
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))

template<typename T, T MOD = 1000000007>
struct Mint {
    T v;

    Mint() : v(0) {}

    Mint(signed v) : v(v) {}

    Mint(long long t) {
        v = t % MOD;
        if (v < 0) v += MOD;
    }

    Mint pow(long long k) {
        Mint res(1), tmp(v);
        while (k) {
            if (k & 1) res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }

    static Mint add_identity() { return Mint(0); }

    static Mint mul_identity() { return Mint(1); }

    Mint inv() { return pow(MOD - 2); }

    Mint &operator+=(Mint a) {
        v += a.v;
        if (v >= MOD)v -= MOD;
        return *this;
    }

    Mint &operator-=(Mint a) {
        v += MOD - a.v;
        if (v >= MOD)v -= MOD;
        return *this;
    }

    Mint &operator*=(Mint a) {
        v = 1LL * v * a.v % MOD;
        return *this;
    }

    Mint &operator/=(Mint a) { return (*this) *= a.inv(); }

    Mint operator+(Mint a) const { return Mint(v) += a; };

    Mint operator-(Mint a) const { return Mint(v) -= a; };

    Mint operator*(Mint a) const { return Mint(v) *= a; };

    Mint operator/(Mint a) const { return Mint(v) /= a; };

    Mint operator-() const { return v ? Mint(MOD - v) : Mint(v); }

    bool operator==(const Mint a) const { return v == a.v; }

    bool operator!=(const Mint a) const { return v != a.v; }

    bool operator<(const Mint a) const { return v < a.v; }

    static Mint comb(long long n, int k) {
        Mint res(1);
        for (int i = 0; i < k; i++) {
            res *= Mint(n - i);
            res /= Mint(i + 1);
        }
        return res;
    }
};

template<typename T>
struct SquareMatrix {

    vector<vector<T>> dat;
    size_t N;

    SquareMatrix() = default;

    SquareMatrix(size_t N, T val = T()) : N(N) {
        dat = vector<vector<T>>(N, vector<T>(N));
        for (size_t i = 0; i < N; i++)
            for (size_t j = 0; j < N; j++)
                dat[i][j] = val;
    }

    SquareMatrix &operator=(const SquareMatrix &a) {
        dat = a.dat;
        return (*this);
    }

    bool operator==(const SquareMatrix &a) const {
        return dat == a.dat;
    }

    size_t size() const { return N; };

    vector<T> &operator[](size_t k) { return dat[k]; };

    const vector<T> &operator[](size_t k) const { return dat[k]; };

    SquareMatrix operator*(const SquareMatrix &B) const {
        SquareMatrix res(N, 0);
        for (size_t i = 0; i < N; i++)
            for (size_t j = 0; j < N; j++)
                for (size_t k = 0; k < N; k++)
                    res[i][j] = res[i][j] + (dat[i][k] * B[k][j]);
        return res;
    }

    SquareMatrix operator+(const SquareMatrix &B) const {
        SquareMatrix res(N, 0);
        for (size_t i = 0; i < N; i++)
            for (size_t j = 0; j < N; j++)
                res[i][j] = dat[i][j] + B[i][j];
        return res;
    }

    SquareMatrix pow(long long n) const {
        SquareMatrix a = *this;
        SquareMatrix res(N, 0);
        for (size_t i = 0; i < N; i++) res[i][i] = 1;
        while (n) {
            if (n & 1) res = res * a;
            a = a * a;
            n >>= 1;
        }
        return res;
    }
};


using mint = Mint<lint, 10>;

int main() {

    lint p, q, r, k;
    cin >> p >> q >> r >> k;
    SquareMatrix<mint> mat(3, 0);
    rep (i, 3) {
        rep (j, 3) {
            mat[i][j] = 0;
        }
    }
    mat[0][0] = mat[0][1] = mat[0][2] = mat[1][0] = mat[2][1] = 1;
    mat = mat.pow(k - 1);
    mint ans = 0;

    ans += mat[2][0] * r;
    ans += mat[2][1] * q;
    ans += mat[2][2] * p;
    cout << ans.v << endl;
    return 0;
}
0