#731059 (PyPy3) No.1810 RGB Biscuits

• 問題: 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

ファイルパターン	結果
sample	AC * 2
other	AC * 20

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX