結果
問題 | No.1810 RGB Biscuits |
ユーザー | NatsubiSogan |
提出日時 | 2022-01-14 23:14:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 260 ms / 2,000 ms |
コード長 | 2,550 bytes |
コンパイル時間 | 158 ms |
コンパイル使用メモリ | 82,232 KB |
実行使用メモリ | 79,888 KB |
最終ジャッジ日時 | 2024-11-20 14:09:07 |
合計ジャッジ時間 | 4,569 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 61 ms
67,668 KB |
testcase_01 | AC | 84 ms
78,524 KB |
testcase_02 | AC | 63 ms
69,356 KB |
testcase_03 | AC | 97 ms
78,764 KB |
testcase_04 | AC | 102 ms
78,580 KB |
testcase_05 | AC | 242 ms
79,440 KB |
testcase_06 | AC | 260 ms
79,544 KB |
testcase_07 | AC | 242 ms
79,240 KB |
testcase_08 | AC | 258 ms
79,212 KB |
testcase_09 | AC | 253 ms
78,776 KB |
testcase_10 | AC | 211 ms
79,160 KB |
testcase_11 | AC | 101 ms
77,888 KB |
testcase_12 | AC | 110 ms
78,972 KB |
testcase_13 | AC | 109 ms
78,388 KB |
testcase_14 | AC | 172 ms
79,648 KB |
testcase_15 | AC | 122 ms
79,140 KB |
testcase_16 | AC | 143 ms
79,888 KB |
testcase_17 | AC | 211 ms
79,352 KB |
testcase_18 | AC | 221 ms
79,200 KB |
testcase_19 | AC | 91 ms
78,056 KB |
testcase_20 | AC | 69 ms
69,136 KB |
testcase_21 | AC | 164 ms
79,356 KB |
ソースコード
import typingclass Matrix:def __init__(self, n: int, m: int, mat: typing.Union[list, None] = None, mod: int = 10 ** 9 + 7) -> None:self.n = nself.m = mself.mat = [[0] * self.m for i in range(self.n)]self.mod = modif mat:for i in range(self.n):self.mat[i] = mat[i]def is_square(self) -> None:return self.n == self.mdef __getitem__(self, key: int) -> int:if isinstance(key, slice):return self.mat[key]else:assert key >= 0return self.mat[key]@classmethoddef id(self, n: int) -> "Matrix":res = Matrix(n, n)for i in range(n):res[i][i] = 1return resdef __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.modreturn Matrix(self.n, self.m, res)def __pos__(self) -> "Matrix":return selfdef __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.modreturn 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.modreturn 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.modreturn 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 *= tmptmp *= tmpk >>= 1return resA, 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)) * xr, g = ans[0][0], ans[1][0]if t % 2: b = A * r + B * gelse: b = 0print((r + g + b) % (10 ** 9 + 7))