結果
| 問題 | No.1595 The Final Digit |
| ユーザー |
 realDivineJK
|
| 提出日時 | 2021-07-25 16:53:28 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
AC
|
| 実行時間 | 22 ms / 2,000 ms |
| コード長 | 11,016 bytes |
| コンパイル時間 | 75 ms |
| コンパイル使用メモリ | 12,040 KB |
| 実行使用メモリ | 9,320 KB |
| 最終ジャッジ日時 | 2023-09-28 06:48:08 |
| 合計ジャッジ時間 | 1,600 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 21 ms
9,136 KB |
| testcase_01 | AC | 20 ms
9,192 KB |
| testcase_02 | AC | 20 ms
9,168 KB |
| testcase_03 | AC | 20 ms
9,168 KB |
| testcase_04 | AC | 21 ms
9,268 KB |
| testcase_05 | AC | 20 ms
9,172 KB |
| testcase_06 | AC | 21 ms
9,168 KB |
| testcase_07 | AC | 22 ms
9,132 KB |
| testcase_08 | AC | 21 ms
9,212 KB |
| testcase_09 | AC | 21 ms
9,136 KB |
| testcase_10 | AC | 20 ms
9,248 KB |
| testcase_11 | AC | 20 ms
9,164 KB |
| testcase_12 | AC | 21 ms
9,164 KB |
| testcase_13 | AC | 21 ms
9,264 KB |
| testcase_14 | AC | 21 ms
9,320 KB |
| testcase_15 | AC | 22 ms
9,156 KB |
| testcase_16 | AC | 22 ms
9,228 KB |
| testcase_17 | AC | 20 ms
9,236 KB |
| testcase_18 | AC | 20 ms
9,136 KB |
| testcase_19 | AC | 21 ms
9,132 KB |
ソースコード
class matrix_collections:
def __init__(self, additional_type=set()):
self.number_type = {int, float}
for i in additional_type:
self.number_type.add(i)
def zeros(self, n, m):
return [[0]*m for _ in range(n)]
def identity(self, n):
return [[(i==j)*1 for j in range(n)] for i in range(n)]
def inved(self, a, modulo):
x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
while l:
x, y, u, v, k, l = u, v, x - u * (k // l), y - v * (k // l), l, k % l
return x % modulo
def ismatrix(self, a):
if type(a) != list:
return False
n = len(a)
flg = True
for i in range(n):
if type(a[i]) != list:
return False
m = len(a[0])
for i in range(n):
if len(a[i]) != m:
flg = False
break
for j in range(m):
if type(a[i][j]) not in self.number_type:
flg = False
break
if not flg:
break
return flg
def mat_sum(self, a, b, weight=1, modulo=0):
if not (self.ismatrix(a) and self.ismatrix(b)):
raise Exception("strange input{}: a = {}, b = {}".format('s'*(self.ismatrix(a)+self.ismatrix(b)==0), a, b))
if len(a) != len(b) or len(a[0]) != len(b[0]):
raise Exception("sizes of matrices are invalid for matrix summation")
n, m = len(a), len(a[0])
res = self.zeros(n, m)
for i in range(n):
for j in range(m):
res[i][j] = a[i][j] + weight*b[i][j]
if modulo:
res[i][j] %= modulo
return res
def mat_prod(self, a, b, modulo=0):
if not (self.ismatrix(a) and self.ismatrix(b)):
raise Exception("strange input{}: a = {}, b = {}".format('s'*(self.ismatrix(a)+self.ismatrix(b)==0), a, b))
if len(a[0]) != len(b):
raise Exception("sizes of matrices are invalid for matrix product")
n, l, m = len(a), len(a[0]), len(b[0])
res = self.zeros(n, m)
for i in range(n):
for j in range(m):
for k in range(l):
res[i][j] += a[i][k] * b[k][j]
if modulo:
res[i][j] %= modulo
return res
def mat_inv(self, a, modulo=0):
if not self.ismatrix(a):
raise Exception("strange input: a = {}".format(a))
if len(a[0]) != len(a):
raise Exception("sizes of matrices are invalid for matrix inverse")
n = len(a)
mid = self.zeros(n, 2*n)
for i in range(n):
mid[i][i+n] = 1
for j in range(n):
if modulo and type(mid[i][j]) != int:
raise Exception("value error: mid[{}][{}] = {}".format(i, j, mid[i][j]))
mid[i][j] = a[i][j]
if modulo:
mid[i][j] %= modulo
for i in range(n):
pnt = i
while mid[pnt][i] == 0:
pnt += 1
if pnt == n:
raise ZeroDivisionError()
for j in range(2*n):
mid[i][j], mid[pnt][j] = mid[pnt][j], mid[i][j]
tmp = mid[i][i]
if modulo:
tmp = self.inved(mid[i][i], modulo)
for j in range(i, 2*n):
if modulo:
mid[i][j] *= tmp
mid[i][j] %= modulo
else:
mid[i][j] /= tmp
for j in range(i+1, n):
tmp1 = mid[j][i]
for k in range(i, 2*n):
if modulo:
mid[j][k] -= tmp1 * mid[i][k]
mid[j][k] %= modulo
else:
mid[j][k] -= tmp1 * mid[i][k]
for i in range(n-1, 0, -1):
for j in range(i, 0, -1):
tmp1 = mid[j-1][i]
for k in range(i, 2*n):
if modulo:
mid[j-1][k] -= tmp1 * mid[i][k]
mid[j-1][k] %= modulo
else:
mid[j-1][k] -= tmp1 * mid[i][k]
res = [[mid[i][j+n] for j in range(n)] for i in range(n)]
return res
def mat_pow(self, a, m, modulo=0):
if not self.ismatrix(a):
raise Exception("strange input: a = {}".format(a))
if len(a[0]) != len(a):
raise Exception("size of matrix is invalid for matrix power")
n = len(a)
res = self.identity(n)
bas = [[a[i][j] for j in range(n)] for i in range(n)]
if m < 0:
m = -m
bas = self.mat_inv(bas, modulo)
tmp = m
while tmp:
if tmp & 1:
res = self.mat_prod(res, bas, modulo)
bas = self.mat_prod(bas, bas, modulo)
tmp >>= 1
return res
def determinant(self, a, modulo=0):
if not self.ismatrix(a):
raise Exception("strange input: a = {}".format(a))
if len(a[0]) != len(a):
raise Exception("size of matrix is invalid for matrix power")
n = len(a)
mid = self.zeros(n, n)
res = 1
for i in range(n):
for j in range(n):
if modulo and type(mid[i][j]) != int:
raise Exception("value error: mid[{}][{}] = {}".format(i, j, mid[i][j]))
mid[i][j] = a[i][j]
if modulo:
mid[i][j] %= modulo
for i in range(n):
pnt = i
while mid[pnt][i] == 0:
pnt += 1
if pnt == n:
res = 0
break
if res == 0:
break
if i != pnt:
if modulo:
res *= modulo - 1
res %= modulo
else:
res *= -1
for j in range(n):
mid[i][j], mid[pnt][j] = mid[pnt][j], mid[i][j]
tmp = mid[i][i]
res *= tmp
if modulo:
res %= modulo
tmp = self.inved(mid[i][i], modulo)
for j in range(i, n):
if modulo:
mid[i][j] *= tmp
mid[i][j] %= modulo
else:
mid[i][j] /= tmp
for j in range(i+1, n):
tmp1 = mid[j][i]
for k in range(i, n):
if modulo:
mid[j][k] -= tmp1 * mid[i][k]
mid[j][k] %= modulo
else:
mid[j][k] -= tmp1 * mid[i][k]
return res
def kronecker_product(self, a, b, modulo=0):
if not (self.ismatrix(a) and self.ismatrix(b)):
raise Exception("strange input{}: a = {}, b = {}".format('s'*(self.ismatrix(a)+self.ismatrix(b)==0), a, b))
n, m, p, q = len(a), len(a[0]), len(b), len(b[0])
res = self.zeros(n*p, m*q)
for i in range(n*p):
for j in range(m*q):
res[i][j] = a[i//p][j//q] * b[i%p][j%q]
if modulo:
if type(res[i][j]) != int:
raise Exception("value error: res[{}][{}] = {}".format(i, j, res[i][j]))
res[i][j] %= modulo
return res
def linear_equation_solver(self, a, b, modulo=0):
if not self.ismatrix(a):
raise Exception("strange input: a = {}".format(a))
if type(b) != list:
raise Exception("strange input: b = {}".format(b))
for i in b:
if type(i) not in self.number_type:
raise Exception("strange input: b = {}".format(b))
n, m, p = len(a), len(a[0]), len(b)
ext_mat = self.zeros(n, m+1)
for i in range(n):
for j in range(m):
ext_mat[i][j] = a[i][j]
if modulo: ext_mat[i][j] %= modulo
if m < p:
for i in range(m, p):
ext_mat.append([0]*(m+1))
for i in range(p):
ext_mat[i][m] = b[i]
if modulo: ext_mat[i][m] %= modulo
pnt = 0
for j in range(m):
x = pnt
flg = True
while x < n:
if ext_mat[x][j]:
flg = False
break
x += 1
if flg: continue
if pnt != x:
for k in range(j, m+1):
ext_mat[pnt][k], ext_mat[x][k] = ext_mat[x][k], ext_mat[pnt][k]
tmp = ext_mat[pnt][j]
ext_mat[pnt][j] = 1
invt = 0
if modulo:
invt = self.inved(tmp, modulo)
for k in range(j+1, m+1):
if modulo:
ext_mat[pnt][k] = invt * ext_mat[pnt][k] % modulo
else:
ext_mat[pnt][k] /= tmp
for l in range(pnt+1, n):
tmp = ext_mat[l][j]
ext_mat[l][j] = 0
if tmp == 0: continue
for k in range(j+1, m+1):
ext_mat[l][k] -= tmp * ext_mat[pnt][k]
if modulo:
ext_mat[l][k] %= modulo
pnt += 1
b = -1
for i in range(n, 0, -1):
flg = True
for j in range(m):
if ext_mat[i-1][j] != 0:
flg = False
break
if flg:
if ext_mat[i-1][m] != 0:
return [[-1]*(m+1)]
else:
b = i - 1
break
solution = [[0]*m for _ in range(m-b)]
idx = [1]*m
fid = [1]*m
for i in range(b, -1, -1):
s = 0
while ext_mat[i][s] == 0:
s += 1
solution[0][s] = ext_mat[i][m]
idx[s] = 0
fid[s] = 0
for j in range(i):
tmp = ext_mat[j][s]
ext_mat[j][s] = 0
for k in range(s+1, m+1):
ext_mat[j][k] -= ext_mat[i][k] * tmp
if modulo:
ext_mat[j][k] %= modulo
if idx[0]:
solution[idx[0]][0] = 1
for i in range(m-1):
idx[i+1] += idx[i]
if fid[i+1]:
solution[idx[i+1]][i+1] = 1
for i in range(b+1):
s = 0
while ext_mat[i][s] == 0:
s += 1
for j in range(s+1, m):
if fid[j]:
solution[idx[j]][s] = -ext_mat[i][j]
if modulo:
solution[idx[j]][s] %= modulo
return solution
mc = matrix_collections()
p, q, r, K = map(int, input().split())
A = [[0, 1, 0], [0, 0, 1], [1, 1, 1]]
A = mc.mat_pow(A, K-1, 10)
print((A[0][0]*p + A[0][1]*q + A[0][2]*r) % 10)