結果
問題 |
No.1810 RGB Biscuits
|
ユーザー |
|
提出日時 | 2025-05-06 00:53:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 171 ms / 2,000 ms |
コード長 | 1,454 bytes |
コンパイル時間 | 556 ms |
コンパイル使用メモリ | 82,312 KB |
実行使用メモリ | 77,540 KB |
最終ジャッジ日時 | 2025-05-06 00:53:56 |
合計ジャッジ時間 | 3,744 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
## https://yukicoder.me/problems/no/1810 MOD = 10 ** 9 + 7 def prod(left, right): new_matrix = [ [0] * 3 for _ in range(3) ] for i in range(3): for j in range(3): for k in range(3): new_matrix[i][j] += (left[i][k] * right[k][j]) % MOD new_matrix[i][j] %= MOD return new_matrix def solve(A, B, T): t = T // 2 matrix1 = [ [1, 0, 0], [0, 1, 0], [A, B, 1] ] matrix2 = [ [0, 0, 1], [1, 0, 0], [0, 0, 0] ] base_matrix = prod(matrix2, matrix1) matrix = [ [1, 0, 0], [0, 1, 0], [0, 0, 1] ] while t > 0: if t % 2 == 1: matrix = prod(base_matrix, matrix) base_matrix = prod(base_matrix, base_matrix) t //= 2 if T % 2 == 1: matrix = prod(matrix1, matrix) vector = [1, 1, 0] new_vector = [0, 0, 0] for i in range(3): for j in range(3): new_vector[i] += (matrix[i][j] * vector[j]) % MOD new_vector[i] %= MOD answer = 0 for i in range(3): answer += new_vector[i] answer %= MOD return answer def main(): A, B = map(int, input().split()) N = int(input()) n_list = [] for _ in range(N): T = int(input()) n_list.append(T) for n in n_list: print(solve(A, B, n)) if __name__ == "__main__": main()