結果

問題 No.1105 Many Triplets
ユーザー sgswsgsw
提出日時 2021-04-23 09:59:02
言語 PyPy3
(7.3.13)
結果
AC  
実行時間 106 ms / 2,000 ms
コード長 5,036 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 87,192 KB
実行使用メモリ 77,760 KB
最終ジャッジ日時 2023-09-17 10:52:51
合計ジャッジ時間 4,166 ms
ジャッジサーバーID
(参考情報)
judge12 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 97 ms
71,792 KB
testcase_01 AC 93 ms
72,376 KB
testcase_02 AC 94 ms
72,396 KB
testcase_03 AC 92 ms
72,108 KB
testcase_04 AC 91 ms
72,096 KB
testcase_05 AC 92 ms
71,800 KB
testcase_06 AC 91 ms
72,164 KB
testcase_07 AC 90 ms
72,056 KB
testcase_08 AC 93 ms
71,952 KB
testcase_09 AC 92 ms
71,952 KB
testcase_10 AC 106 ms
77,552 KB
testcase_11 AC 104 ms
77,276 KB
testcase_12 AC 102 ms
77,228 KB
testcase_13 AC 103 ms
77,344 KB
testcase_14 AC 102 ms
77,164 KB
testcase_15 AC 100 ms
77,340 KB
testcase_16 AC 104 ms
77,760 KB
testcase_17 AC 103 ms
77,548 KB
testcase_18 AC 103 ms
77,576 KB
testcase_19 AC 103 ms
77,316 KB
testcase_20 AC 89 ms
72,164 KB
testcase_21 AC 89 ms
72,120 KB
testcase_22 AC 88 ms
72,232 KB
testcase_23 AC 89 ms
72,116 KB
testcase_24 AC 92 ms
72,208 KB
testcase_25 AC 90 ms
71,924 KB
testcase_26 AC 89 ms
71,804 KB
testcase_27 AC 90 ms
71,804 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

import random
import sys
"""
new library check -> atcoder/math/matrix
"""


class Matrix:
    def __init__(self, m, n):
        self.row = m
        self.column = n
        self.array = [[0]*(n) for _ in range(m)]

    @classmethod
    def given_array(cls, LIST):
        try:
            column = len(LIST[0])
            row = len(LIST)
            res = Matrix(row, column)
            for i in range(row):
                for j in range(column):
                    res.array[i][j] = LIST[i][j]
            return res
        except:
            raise ValueError("error!")

    @classmethod
    def eye(cls, m):
        res = Matrix(m, m)
        for i in range(m):
            res.array[i][i] = 1
        return res

    def show(self):
        for i in range(self.row):
            print(*self.array[i])
        return True

    def get(self, i, j):
        assert 0 <= i < self.row and 0 <= j < self.column
        return self.array[i][j]

    def __add__(self, other):
        if not isinstance(other, Matrix):
            return self.__addval__(other)

        assert self.row == other.row and self.column == other.column
        res = Matrix(self.row, self.column)
        for i in range(self.row):
            for j in range(self.column):
                res.array[i][j] = self.array[i][j] + other.array[i][j]
        return res

    def __addval__(self, other):
        assert isinstance(other, int) or isinstance(other, float), "ValueError"
        res = Matrix(self.row, self.column)
        for i in range(self.row):
            for j in range(self.column):
                res.array[i][j] = self.array[i][j] + other
        return res

    def __sub__(self, other):
        if not isinstance(other, Matrix):
            assert isinstance(other, int) or isinstance(
                other, float), "ValueError"
            return self.__addval__(-other)

        assert self.row == other.row and self.column == other.column
        res = Matrix(self.row, self.column)
        for i in range(self.row):
            for j in range(self.column):
                res.array[i][j] = self.array[i][j] - other.array[i][j]
        return res

    def __mul__(self, other):
        if not isinstance(other, Matrix):
            return self.__mulval__(other)

        assert self.column == other.row

        res = Matrix(self.row, other.column)
        for i in range(self.row):
            for j in range(other.column):
                res.array[i][j] = sum(self.array[i][_]*other.array[_][j]
                                      for _ in range(self.column))
        return res

    def __mulval__(self, other):
        assert isinstance(other, int) or isinstance(other, float), "ValueError"
        res = Matrix(self.row, self.column)
        for i in range(self.row):
            for j in range(self.column):
                res.array[i][j] = self.array[i][j] * other
        return res

    def __pow__(self, ord):
        assert self.row == self.column
        assert isinstance(ord, int), "ValueError"
        if ord == 0:
            return self.eye(self.row)
        if ord == 1:
            return self
        res = self.__pow__(ord >> 1)
        if ord % 2 == 0:
            return res.__mul__(res)
        return self.__mul__(self.__pow__(ord - 1))

    def powMod(self, ord, MODULO):
        assert self.row == self.column
        assert isinstance(ord, int), "ValueError"
        if ord == 0:
            return self.eye(self.row)
        if ord == 1:
            return self
        res = self.powMod(ord >> 1, MODULO)
        res *= res
        res %= MODULO
        if ord % 2 == 0:
            return res
        return (res * self) % MODULO

    def __mod__(self, modulo):
        res = Matrix(self.row, self.column)
        for i in range(self.row):
            for j in range(self.column):
                res.array[i][j] = self.array[i][j] % modulo
        return res

    def __eq__(self, other):
        if self.row != other.row or self.column != other.column:
            return False
        for i in range(self.row):
            for j in range(self.column):
                if self.array[i][j] != other.array[i][j]:
                    return False
        return True

    def __radd__(self, other):
        return __add__(other, self)

    def __rsub__(self, other):
        return __sub__(other, self)

    def __rmul__(self, other):
        return __mul__(other, self)

    def T(self):
        res = Matrix(self.column, self.row)
        for i in range(self.row):
            for j in range(self.column):
                res.array[j][i] = self.array[i][j]
        return res


def input():
    return sys.stdin.readline().rstrip()


def main():
    n = int(input())
    a, b, c = map(int, input().split())
    MOD = int(1e9 + 7)
    vec = [[1, -1, 0], [0, 1, -1], [-1, 0, 1]]
    A = Matrix.given_array(vec)
    basement = Matrix.given_array([[a], [b], [c]])
    ans = A.powMod(n - 1, MOD) * basement
    ans %= MOD
    ans = ans.T()
    ans.show()
    return


if __name__ == "__main__":
    main()
0