結果

問題 No.1105 Many Triplets
ユーザー sgswsgsw
提出日時 2021-04-23 09:52:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,230 bytes
コンパイル時間 303 ms
コンパイル使用メモリ 87,116 KB
実行使用メモリ 100,060 KB
最終ジャッジ日時 2023-09-17 10:52:42
合計ジャッジ時間 5,937 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 147 ms
83,256 KB
testcase_01 AC 191 ms
79,608 KB
testcase_02 AC 111 ms
78,180 KB
testcase_03 AC 138 ms
78,936 KB
testcase_04 AC 114 ms
78,228 KB
testcase_05 AC 141 ms
78,580 KB
testcase_06 AC 123 ms
78,492 KB
testcase_07 AC 101 ms
77,460 KB
testcase_08 AC 134 ms
78,560 KB
testcase_09 AC 105 ms
77,240 KB
testcase_10 TLE -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
権限があれば一括ダウンロードができます

ソースコード

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)
        if ord % 2 == 0:
            return res.__mul__(res) % MODULO
        return self.__mul__(self.powMod(ord - 1, MODULO)) % 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 MOD(self, modulo):
        for i in range(self.row):
            for j in range(self.column):
                res.array[i][j] = self.array[i][j] % modulo
        return True

    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