結果

問題 No.1595 The Final Digit
ユーザー toyuzukotoyuzuko
提出日時 2021-07-09 21:45:53
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 85 ms / 2,000 ms
コード長 8,093 bytes
コンパイル時間 314 ms
コンパイル使用メモリ 86,944 KB
実行使用メモリ 76,672 KB
最終ジャッジ日時 2023-09-14 08:23:00
合計ジャッジ時間 2,890 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 76 ms
71,180 KB
testcase_01 AC 76 ms
71,464 KB
testcase_02 AC 75 ms
71,176 KB
testcase_03 AC 81 ms
71,188 KB
testcase_04 AC 80 ms
75,628 KB
testcase_05 AC 82 ms
75,792 KB
testcase_06 AC 84 ms
76,520 KB
testcase_07 AC 85 ms
76,492 KB
testcase_08 AC 74 ms
71,264 KB
testcase_09 AC 75 ms
71,240 KB
testcase_10 AC 77 ms
71,172 KB
testcase_11 AC 77 ms
71,096 KB
testcase_12 AC 76 ms
71,176 KB
testcase_13 AC 76 ms
71,260 KB
testcase_14 AC 83 ms
76,324 KB
testcase_15 AC 82 ms
76,672 KB
testcase_16 AC 84 ms
76,664 KB
testcase_17 AC 77 ms
71,340 KB
testcase_18 AC 77 ms
71,332 KB
testcase_19 AC 84 ms
76,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

MOD = 10

class Matrix():
    def __init__(self, n, m, mat=None):
        self.n = n
        self.m = m
        self.mat = [[0] * self.m for _ in range(self.n)]
        if mat:
            assert len(mat) == n and len(mat[0]) == m
            for i in range(self.n):
                self.mat[i] = mat[i].copy()

    def is_square(self):
        return self.n == self.m

    def __getitem__(self, key):
        if isinstance(key, slice):
            return self.mat[key]
        else:
            assert key >= 0
            return self.mat[key]

    def id(n):
        res = Matrix(n, n)
        for i in range(n):
            res[i][i] = 1
        return res

    def __len__(self):
        return len(self.mat)

    def __str__(self):
        return '\n'.join(' '.join(map(str, self[i])) for i in range(self.n))

    def times(self, k):
        res = [[0] * self.m for _ in range(self.n)]
        for i in range(self.n):
            res_i, self_i = res[i], self[i]
            for j in range(self.m):
                res_i[j] = k * self_i[j] % MOD
        return Matrix(self.n, self.m, res)

    def __pos__(self):
        return self

    def __neg__(self):
        return self.times(-1)

    def __add__(self, other):
        assert self.n == other.n and self.m == other.m
        res = [[0] * self.m for _ in range(self.n)]
        for i in range(self.n):
            res_i, self_i, other_i = res[i], self[i], other[i]
            for j in range(self.m):
                res_i[j] = (self_i[j] + other_i[j]) % MOD
        return Matrix(self.n, self.m, res)

    def __sub__(self, other):
        assert self.n == other.n and self.m == other.m
        res = [[0] * self.m for _ in range(self.n)]
        for i in range(self.n):
            res_i, self_i, other_i = res[i], self[i], other[i]
            for j in range(self.m):
                res_i[j] = (self_i[j] - other_i[j]) % MOD
        return Matrix(self.n, self.m, res)

    def __mul__(self, other):
        if other.__class__ == Matrix:
            assert self.m == other.n
            res = [[0] * other.m for _ in range(self.n)]
            for i in range(self.n):
                res_i, self_i = res[i], self[i]
                for k in range(self.m):
                    self_ik, other_k = self_i[k], other[k]
                    for j in range(other.m):
                        res_i[j] += self_ik * other_k[j]
                        res_i[j] %= MOD
            return Matrix(self.n, other.m, res)
        else:
            return self.times(other)

    def __rmul__(self, other):
        return self.times(other)

    def __pow__(self, k):
        assert self.is_square()
        tmp = Matrix(self.n, self.n, self.mat)
        res = Matrix.id(self.n)
        while k:
            if k & 1:
                res *= tmp
            tmp *= tmp
            k >>= 1
        return res

    def determinant(self):
        assert self.is_square()
        res = 1
        tmp = Matrix(self.n, self.n, self.mat)
        for j in range(self.n):
            if tmp[j][j] == 0:
                for i in range(j + 1, self.n):
                    if tmp[i][j]:
                        break
                else:
                    return 0
                tmp.mat[j], tmp.mat[i] = tmp.mat[i], tmp.mat[j]
                res *= -1
            tmp_j = tmp[j]
            inv = pow(tmp_j[j], MOD - 2, MOD)
            for i in range(j + 1, self.n):
                tmp_i = tmp[i]
                c = -inv * tmp_i[j] % MOD
                for k in range(self.n):
                    tmp_i[k] += c * tmp_j[k]
                    tmp_i[k] %= MOD
        for i in range(self.n):
            res *= tmp[i][i]
            res %= MOD
        return res

    def inverse(self):
        assert self.is_square()
        res = Matrix.id(self.n)
        tmp = Matrix(self.n, self.n, self.mat)
        for j in range(self.n):
            if tmp[j][j] == 0:
                for i in range(j + 1, self.n):
                    if tmp[i][j]:
                        break
                else:
                    return -1
                tmp.mat[j], tmp.mat[i] = tmp.mat[i], tmp.mat[j]
                res.mat[j], res.mat[i] = res.mat[i], res.mat[j]
            tmp_j, res_j = tmp[j], res[j]
            inv = pow(tmp_j[j], MOD - 2, MOD)
            for k in range(self.n):
                tmp_j[k] *= inv
                tmp_j[k] %= MOD
                res_j[k] *= inv
                res_j[k] %= MOD
            for i in range(self.n):
                if i == j: continue
                c = tmp[i][j]
                tmp_i, res_i = tmp[i], res[i]
                for k in range(self.n):
                    tmp_i[k] -= tmp_j[k] * c
                    tmp_i[k] %= MOD
                    res_i[k] -= res_j[k] * c
                    res_i[k] %= MOD
        return res

    def characteristic_polynomial(self):
        assert self.is_square()
        tmp = Matrix(self.n, self.n, self.mat)
        for j in range(self.n - 2):
            for i in range(j + 1, self.n):
                if tmp[i][j]:
                    break
            else:
                continue
            tmp.mat[j + 1], tmp.mat[i] = tmp.mat[i], tmp.mat[j + 1]
            for k in range(self.n):
                tmp.mat[k][j + 1], tmp.mat[k][i] = tmp.mat[k][i], tmp.mat[k][j + 1]
            if tmp[j + 1][j]:
                inv = pow(tmp[j + 1][j], MOD - 2, MOD)
                for i in range(j + 2, self.n):
                    c = inv * tmp[i][j] % MOD
                    for k in range(j, self.n):
                        tmp[i][k] -= c * tmp[j + 1][k]
                        tmp[i][k] %= MOD
                    for k in range(self.n):
                        tmp[k][j + 1] += c * tmp[k][i]
                        tmp[k][j + 1] %= MOD
        dp = [[0] * (i + 1) for i in range(self.n + 1)]
        dp[0][0] = 1
        for i in range(self.n):
            for k in range(i + 1):
                dp[i + 1][k + 1] = dp[i][k]
            for k in range(i + 1):
                dp[i + 1][k] += tmp[i][i] * dp[i][k]
                dp[i + 1][k] %= MOD
            p = 1
            for j in range(i)[::-1]:
                p *= -tmp[j + 1][j]
                p %= MOD
                c = p * tmp[j][i] % MOD
                for k in range(j + 1):
                    dp[i + 1][k] += c * dp[j][k]
                    dp[i + 1][k] %= MOD
        res = dp[-1]
        for i in range(self.n + 1):
            if i & 1:
                res[~i] *= -1
                res[~i] %= MOD
        return res

    def linear_equations(self, vec):
        assert self.n == len(vec)
        aug = [self[i] + [vec[i]] for i in range(self.n)]
        rank = 0
        p = []
        q = []
        for j in range(self.m + 1):
            for i in range(rank, self.n):
                if aug[i][j]: break
            else:
                q.append(j)
                continue
            if j == self.m: return -1, [], []
            p.append(j)
            aug[rank], aug[i] = aug[i], aug[rank]
            inv = pow(aug[rank][j], MOD - 2, MOD)
            aug_rank = aug[rank]
            for k in range(self.m + 1):
                aug_rank[k] *= inv
                aug_rank[k] %= MOD
            for i in range(self.n):
                if i == rank: continue
                aug_i = aug[i]
                c = -aug_i[j]
                for k in range(self.m + 1):
                    aug_i[k] += c * aug_rank[k]
                    aug_i[k] %= MOD
            rank += 1
        dim = self.m - rank
        sol = [0] * self.m
        for i in range(rank):
            sol[p[i]] = aug[i][-1]
        vecs = [[0] * self.m for _ in range(dim)]
        for i in range(dim):
            vecs[i][q[i]] = 1
        for i in range(dim):
            vecs_i = vecs[i]
            for j in range(rank):
                vecs_i[p[j]] = -aug[j][q[i]] % MOD
        return dim, sol, vecs
p, q, r, K = map(int, input().split())
p %= 10
q %= 10
r %= 10
mat = [[0, 1, 0], [0, 0, 1], [1, 1, 1]]
vec = [p, q, r]
M = Matrix(3, 3, mat)**(K - 3)
res = (M[2][0] * p + M[2][1] * q + M[2][2] * r) % 10
print(res)
0