結果
| 問題 | No.1595 The Final Digit |
| コンテスト | |
| ユーザー |
 toyuzuko
|
| 提出日時 | 2021-07-09 21:45:53 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 52 ms / 2,000 ms |
| コード長 | 8,093 bytes |
| コンパイル時間 | 175 ms |
| コンパイル使用メモリ | 82,396 KB |
| 実行使用メモリ | 63,104 KB |
| 最終ジャッジ日時 | 2024-07-01 15:47:07 |
| 合計ジャッジ時間 | 1,866 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
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)