結果
| 問題 | No.1810 RGB Biscuits |
| ユーザー |
 Shirotsume
|
| 提出日時 | 2022-06-24 00:50:51 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 295 ms / 2,000 ms |
| コード長 | 6,826 bytes |
| コンパイル時間 | 217 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 78,024 KB |
| 最終ジャッジ日時 | 2024-04-25 08:48:14 |
| 合計ジャッジ時間 | 4,394 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 49 ms
54,400 KB |
| testcase_01 | AC | 71 ms
74,752 KB |
| testcase_02 | AC | 58 ms
65,920 KB |
| testcase_03 | AC | 100 ms
77,056 KB |
| testcase_04 | AC | 96 ms
76,800 KB |
| testcase_05 | AC | 246 ms
77,696 KB |
| testcase_06 | AC | 283 ms
77,668 KB |
| testcase_07 | AC | 295 ms
78,024 KB |
| testcase_08 | AC | 272 ms
77,568 KB |
| testcase_09 | AC | 274 ms
77,568 KB |
| testcase_10 | AC | 207 ms
77,276 KB |
| testcase_11 | AC | 119 ms
77,056 KB |
| testcase_12 | AC | 104 ms
76,672 KB |
| testcase_13 | AC | 113 ms
77,312 KB |
| testcase_14 | AC | 146 ms
77,184 KB |
| testcase_15 | AC | 120 ms
77,440 KB |
| testcase_16 | AC | 120 ms
77,184 KB |
| testcase_17 | AC | 192 ms
77,776 KB |
| testcase_18 | AC | 199 ms
77,404 KB |
| testcase_19 | AC | 84 ms
76,032 KB |
| testcase_20 | AC | 58 ms
67,200 KB |
| testcase_21 | AC | 139 ms
77,184 KB |
ソースコード
import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
INF = 2 ** 63 - 1
mod = 10 ** 9 + 7
class Matrix():
def __init__(self, r, c, mod = 10 ** 9 + 7):
self.r = r
self.c = c
self.A = [[0] * self.c for _ in range(self.r)]
self.mod = mod
def makeone(self, r = 1):
A = Matrix(r, r, self.mod)
for i in range(r):
A[i, i] = 1
return A
def __getitem__(self, key):
rnow, cnow = key
return self.A[rnow][cnow]
def __setitem__(self, key, value):
rnow, cnow = key
self.A[rnow][cnow] = value
def __add__(self, other):
assert self.r == other.r and self.c == other.c
ret = Matrix(self.r, self.c)
for i in range(self.r):
for j in range(self.c):
ret[i, j] = self[i, j] + other[i, j]
ret[i, j] %= self.mod
return ret
def __sub__(self, other):
assert self.r == other.r and self.c == other.c
ret = Matrix(self.r, self.c)
for i in range(self.r):
for j in range(self.c):
ret[i, j] = self[i, j] - other[i, j]
ret[i, j] %= self.mod
return ret
def __mul__(self, other):
if isinstance(other, int):
ret = Matrix(self.r, self.c)
for i in range(self.r):
for j in range(self.c):
ret[i, j] = self[i, j] * other
ret[i, j] %= self.mod
assert self.c == other.r
ret = Matrix(self.r, other.c)
for i in range(self.r):
for j in range(self.c):
for k in range(other.c):
ret[i, k] += self[i, j] * other[j, k]
ret[i, k] %= self.mod
return ret
def pow(self, x):
assert isinstance(x, int) and x >= 0
assert self.r == self.c
if x == 0:
return self.makeone(self.c)
else:
ret = self.makeone(self.c)
now = self
while x > 0:
if x % 2:
ret *= now
now *= now
x //= 2
return ret
def augment(self, other):
assert self.r == other.r
X = Matrix(self.r, self.c + other.c, mod = self.mod)
for i in range(self.r):
for j in range(self.c):
X[i, j] = self[i, j]
for j in range(other.c):
X[i, j + self.c] = other[i, j]
return X
def diminish(self, c):
X = []
for i in range(self.r):
X.append((self.A[i][:c]))
return Matrix(self.r, c, mod = self.mod, A = X)
def hakidashi(self):
for i in range(self.c):
for j in range(i + 1, self.r):
if self[j, i] != 0:
for k in range(self.c):
self[j, k], self[i, k] = self[i, k], self[j, k]
break
for i in range(self.r):
for j in range(self.c):
if self[i, j] != 0:
break
else:
continue
K = pow(self[i, j], self.mod - 2, self.mod)
for to in range(self.c):
self[i, to] *= K
self[i, to] %= self.mod
for i2 in range(self.r):
if i == i2:
continue
time = self[i2, j]
for j2 in range(self.c):
self[i2, j2] -= time * self[i, j2]
self[i2, j2] %= self.mod
return self
def inv(self):
assert self.c == self.r
one = Matrix.makeone(r = self.r)
new = self.augment(one)
new.hakidashi()
for i in range(self.r):
for j in range(self.c):
if i == j:
if new[i, j] != 1:
return 0, new
else:
if new[i, j] != 0:
return 0, new
X = Matrix(self.r, self.c)
for i in range(self.r):
for j in range(self.c):
X[i, j] = new[i, j + self.c]
return 1, X
def lineareq(self, b):
assert self.r == b.r
assert b.c == 1
Y = self.augment(b)
Y = Y.hakidashi()
B = [[0] * self.c for _ in range(self.c)]
ans = [0] * self.c
flag = [0] * self.c
for i in range(self.r):
j = 0
while j < self.c and Y[i, j] == 0:
j += 1
if j == self.c:
if Y[i, -1] != 0:
return None, None
continue
flag[j] = 1
ans[j] = Y[i, -1]
for k in range(j + 1, self.c):
if Y[i, k] % self.mod != 0:
B[k][j] = (-Y[i, k])% self.mod
flag[k] = -1
for i in range(self.c):
if flag[i] != 1:
B[i][i] = 1
B=[B[i] for i in range(self.c) if flag[i] != 1]
return ans,B
def rank(self):
new = self.hakidashi()
ret = 0
for i in range(self.r):
for j in range(self.c):
if new[i, j] != 0:
ret += 1
break
return ret
def det(self):
ret = 1
a = self
for i in range(self.r):
if a[i, i] == 0:
for j in range(i + 1, self.r):
if a[j, i]:
break
else:
return 0
for k in range(self.r):
a[j, k], a[i, k] = a[i, k], a[j, k]
ret *= -1
ret %= self.mod
for j in range(self.r):
if i < j:
buf = a[j, i] * (pow(a[i, i], self.mod - 2, self.mod))
buf %= self.mod
for k in range(self.r):
a[j, k] -= a[i, k] * buf
a[j, k] %= self.mod
for i in range(self.r):
ret *= a[i, i]
ret %= self.mod
return ret
def print(self):
for v in self.A:
print(*v)
a, b = mi()
q = ii()
def f(k):
A = Matrix(2, 2, mod)
A[0, 0] = a
A[0, 1] = b
A[1, 0] = 1
A = A.pow(k)
V = Matrix(2, 1, mod)
V[0, 0] = V[1, 0] = 1
A *= V
return A[1, 0] % mod
for _ in range(q):
x = ii()
if x % 2 == 0:
ans = f(x // 2) + f(x // 2 + 1)
else:
ans = f(x // 2) + f(x // 2 + 1) + f(x // 2 + 2)
ans %= mod
print(ans)