結果
問題 | No.1595 The Final Digit |
ユーザー | zkou |
提出日時 | 2021-07-09 22:59:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 82 ms / 2,000 ms |
コード長 | 1,903 bytes |
コンパイル時間 | 286 ms |
コンパイル使用メモリ | 87,156 KB |
実行使用メモリ | 76,608 KB |
最終ジャッジ日時 | 2023-09-14 10:33:48 |
合計ジャッジ時間 | 2,872 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 72 ms
71,176 KB |
testcase_01 | AC | 73 ms
71,184 KB |
testcase_02 | AC | 72 ms
71,400 KB |
testcase_03 | AC | 73 ms
71,552 KB |
testcase_04 | AC | 79 ms
75,972 KB |
testcase_05 | AC | 81 ms
75,968 KB |
testcase_06 | AC | 82 ms
76,296 KB |
testcase_07 | AC | 80 ms
76,440 KB |
testcase_08 | AC | 73 ms
71,556 KB |
testcase_09 | AC | 72 ms
71,400 KB |
testcase_10 | AC | 72 ms
71,560 KB |
testcase_11 | AC | 73 ms
71,308 KB |
testcase_12 | AC | 74 ms
71,204 KB |
testcase_13 | AC | 73 ms
71,276 KB |
testcase_14 | AC | 80 ms
76,572 KB |
testcase_15 | AC | 79 ms
76,408 KB |
testcase_16 | AC | 81 ms
76,296 KB |
testcase_17 | AC | 72 ms
71,560 KB |
testcase_18 | AC | 73 ms
71,396 KB |
testcase_19 | AC | 79 ms
76,608 KB |
ソースコード
_mat_mod = 10 class matrix: def __init__(self, r, c, ID=0): self.r = r self.c = c self.data = [[0]*c for _ in range(r)] if ID: if r != c: raise Exception("Error! r: "+str(r)+" != c: "+str(c)) for i in range(r): self.data[i][i] = ID def __mul__(self, other): r1 = self.r c1 = self.c if type(other) == int: ret = self for i in range(r1): for j in range(c1): ret.data[i][j] *= other ret.data[i][j] %= _mat_mod else: r2 = other.r c2 = other.c if c1 != r2: raise Exception("Error! c1: "+str(c1)+" != r2: "+str(r2)) ret = matrix(r1, c2) for i in range(r1): for k in range(c1): for j in range(c2): ret.data[i][j] += self.data[i][k] * other.data[k][j] ret.data[i][j] %= _mat_mod return ret def __rmul__(self, other): return self*other def __pow__(self, n): r = self.r c = self.c x = self if r != c: raise Exception("Error! r: "+str(r)+" != c: "+str(c)) ret = matrix(r, c, 1) while n: if n & 1: ret *= x x *= x n >>= 1 return ret def __getitem__(self, key): return self.data[key] def __str__(self): return "\n".join([" ".join(map(str, self.data[i])) for i in range(self.r)]) p, q, r, K = list(map(int, input().split())) # AN 1 1 1 AN-1 # AN-1 = 1 AN-2 # AN-2 1 AN-3 M = matrix(3, 3) M[0][0] = 1 M[0][1] = 1 M[0][2] = 1 M[1][0] = 1 M[2][1] = 1 v = matrix(3, 1) v[0][0] = r v[1][0] = q v[2][0] = p print((M ** (K - 3) * v)[0][0])