結果
問題 | No.1810 RGB Biscuits |
ユーザー | NatsubiSogan |
提出日時 | 2022-01-14 23:14:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 236 ms / 2,000 ms |
コード長 | 2,550 bytes |
コンパイル時間 | 248 ms |
コンパイル使用メモリ | 82,260 KB |
実行使用メモリ | 80,120 KB |
最終ジャッジ日時 | 2024-04-30 17:09:29 |
合計ジャッジ時間 | 4,258 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 56 ms
68,468 KB |
testcase_01 | AC | 75 ms
78,332 KB |
testcase_02 | AC | 58 ms
69,644 KB |
testcase_03 | AC | 92 ms
78,440 KB |
testcase_04 | AC | 96 ms
78,532 KB |
testcase_05 | AC | 224 ms
79,564 KB |
testcase_06 | AC | 224 ms
80,056 KB |
testcase_07 | AC | 222 ms
79,572 KB |
testcase_08 | AC | 236 ms
79,488 KB |
testcase_09 | AC | 228 ms
79,392 KB |
testcase_10 | AC | 193 ms
79,388 KB |
testcase_11 | AC | 91 ms
78,500 KB |
testcase_12 | AC | 98 ms
78,596 KB |
testcase_13 | AC | 98 ms
78,728 KB |
testcase_14 | AC | 142 ms
80,120 KB |
testcase_15 | AC | 112 ms
79,696 KB |
testcase_16 | AC | 121 ms
79,404 KB |
testcase_17 | AC | 182 ms
79,808 KB |
testcase_18 | AC | 200 ms
79,780 KB |
testcase_19 | AC | 86 ms
78,448 KB |
testcase_20 | AC | 61 ms
70,576 KB |
testcase_21 | AC | 142 ms
79,744 KB |
ソースコード
import typing class Matrix: def __init__(self, n: int, m: int, mat: typing.Union[list, None] = None, mod: int = 10 ** 9 + 7) -> None: self.n = n self.m = m self.mat = [[0] * self.m for i in range(self.n)] self.mod = mod if mat: for i in range(self.n): self.mat[i] = mat[i] def is_square(self) -> None: return self.n == self.m def __getitem__(self, key: int) -> int: if isinstance(key, slice): return self.mat[key] else: assert key >= 0 return self.mat[key] @classmethod def id(self, n: int) -> "Matrix": res = Matrix(n, n) for i in range(n): res[i][i] = 1 return res def __len__(self) -> int: return len(self.mat) def __str__(self) -> str: return "\n".join(" ".join(map(str, self[i])) for i in range(self.n)) def times(self, k: int) -> "Matrix": res = [[0] * self.m for i in range(self.n)] for i in range(self.n): for j in range(self.m): res[i][j] = k * self[i][j] % self.mod return Matrix(self.n, self.m, res) def __pos__(self) -> "Matrix": return self def __neg__(self) -> "Matrix": return self.times(-1) def __add__(self, other: "Matrix") -> "Matrix": res = [[0] * self.m for i in range(self.n)] for i in range(self.n): for j in range(self.m): res[i][j] = (self[i][j] + other[i][j]) % self.mod return Matrix(self.n, self.m, res) def __sub__(self, other: "Matrix") -> "Matrix": res = [[0] * self.m for i in range(self.n)] for i in range(self.n): for j in range(self.m): res[i][j] = (self[i][j] - other[i][j]) % self.mod return Matrix(self.n, self.m, res) def __mul__(self, other: typing.Union["Matrix", int]) -> "Matrix": if other.__class__ == Matrix: res = [[0] * other.m for i in range(self.n)] for i in range(self.n): for k in range(self.m): for j in range(other.m): res[i][j] += self[i][k] * other[k][j] res[i][j] %= self.mod return Matrix(self.n, other.m, res) else: return self.times(other) def __rmul__(self, other: typing.Union["Matrix", int]) -> "Matrix": return self.times(other) def __pow__(self, k: int) -> "Matrix": tmp = Matrix(self.n, self.n, self.mat) res = self.id(self.n) while k: if k & 1: res *= tmp tmp *= tmp k >>= 1 return res A, B = map(int, input().split()) n = int(input()) for _ in range(n): t = int(input()) x = Matrix(2, 1, [[1], [1]]) M = Matrix(2, 2, [[A, B], [1, 0]]) if t <= 1: ans = x[:] else: ans = (M ** (t // 2)) * x r, g = ans[0][0], ans[1][0] if t % 2: b = A * r + B * g else: b = 0 print((r + g + b) % (10 ** 9 + 7))