結果
問題 | No.1810 RGB Biscuits |
ユーザー | MasKoaTS |
提出日時 | 2022-11-29 22:58:32 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,275 bytes |
コンパイル時間 | 193 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 79,404 KB |
最終ジャッジ日時 | 2024-04-16 13:36:21 |
合計ジャッジ時間 | 5,502 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 49 ms
52,864 KB |
testcase_01 | AC | 80 ms
71,168 KB |
testcase_02 | AC | 47 ms
54,144 KB |
testcase_03 | AC | 107 ms
76,928 KB |
testcase_04 | AC | 110 ms
76,288 KB |
testcase_05 | WA | - |
testcase_06 | AC | 374 ms
78,500 KB |
testcase_07 | AC | 359 ms
78,416 KB |
testcase_08 | AC | 366 ms
79,404 KB |
testcase_09 | AC | 350 ms
78,492 KB |
testcase_10 | WA | - |
testcase_11 | AC | 125 ms
76,800 KB |
testcase_12 | AC | 115 ms
76,672 KB |
testcase_13 | AC | 121 ms
77,056 KB |
testcase_14 | AC | 204 ms
77,896 KB |
testcase_15 | AC | 138 ms
76,800 KB |
testcase_16 | AC | 175 ms
77,440 KB |
testcase_17 | AC | 257 ms
78,796 KB |
testcase_18 | AC | 266 ms
78,596 KB |
testcase_19 | AC | 114 ms
76,928 KB |
testcase_20 | AC | 50 ms
54,656 KB |
testcase_21 | AC | 187 ms
78,592 KB |
ソースコード
import sys input = sys.stdin.readline class ModInt: mod = 998244353 def __init__(self, x): self.x = x % ModInt.mod @classmethod def set_mod(cls, mod: int) -> None: ModInt.mod = mod def __str__(self): return str(self.x) __repr__ = __str__ def __add__(self, other): return (ModInt(self.x + other.x) if isinstance(other, ModInt) else ModInt(self.x + other)) def __sub__(self, other): return (ModInt(self.x - other.x) if isinstance(other, ModInt) else ModInt(self.x - other)) def __mul__(self, other): return (ModInt(self.x * other.x) if isinstance(other, ModInt) else ModInt(self.x * other)) def __truediv__(self, other): return (ModInt(self.x * pow(other.x, ModInt.mod - 2, ModInt.mod)) if instance(other, ModInt) else ModInt(self.x * pow(other, ModInt.mod - 2, ModInt.mod))) def __pow__(self, other): return ModInt(pow(self.x, other.x, ModInt.mod)) if isinstance(other, ModInt) else ModInt(pow(self.x, other, ModInt.mod)) __radd__ = __add__ def __rsub__(self, other): return (ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)) __rmul__ = __mul__ def __rtruediv__(self, other): return (ModInt(other.x * pow(self.x, ModInt.mod - 2, ModInt.mod)) if instance(other, ModInt) else ModInt(other * pow(self.x, ModInt.mod - 2, ModInt.mod))) def __rpow__(self, other): return ModInt(pow(other.x, self.x, ModInt.mod)) if instance(other, ModInt) else ModInt(pow(other, self.x, ModInt.mod)) def __iadd__(self, other): self = self + other return self def __isub__(self, other): self = self - other return self def __imul__(self, other): self = self * other return self def __itruediv__(self, other): self = self / other return self class Matrix: def __init__(self, A: list): if not(A and isinstance(A[0], list)): A = [A] self.A = A self.row = len(A) self.col = len(A[0]) self.I = None def set_A(self, A: list) -> None: self.A = A def set_I(self, I) -> None: self.I = I def __str__(self): return str(self.A) __repr__ = __str__ def __add__(self, other): ret = Matrix(self) for i in range(self.row): for j in range(self.col): ret.A[i][j] = self.A[i][j] + other.A[i][j] return ret def __sub__(self, other): ret = Matrix(self) for i in range(self.row): for j in range(self.col): ret.A[i][j] = self.A[i][j] - other.A[i][j] return ret def __mul__(self, other): assert(self.col == other.row) ret = Matrix([[0]*other.col for _ in [0]*self.row]) for i in range(self.row): for j in range(other.col): ret.A[i][j] = sum(self.A[i][k] * other.A[k][j] for k in range(self.col)) return ret def __pow__(self, other: int): mat = self ret = Matrix(self.I) n = other while(n): if(n & 1): ret = mat * ret mat = mat * mat n >>= 1 return ret """ Main Code """ a, b = map(int, input().split()) n = int(input()) P = Matrix([[ModInt(a), ModInt(b)], [ModInt(1), ModInt(0)]]) P.set_I([[ModInt(1), ModInt(0)], [ModInt(0), ModInt(1)]]) v = Matrix([[ModInt(1)], [ModInt(1)]]) ModInt.set_mod(10 ** 9 + 7) for t in [int(input()) for _ in [0]*n]: k = t >> 1 r = t & 1 v1 = (P ** k) * v v2 = P * v1 if(r == 1): print(v1.A[0][0] + v1.A[1][0] + v2.A[0][0]) else: print(v1.A[0][0] + v1.A[1][0])