結果

問題 No.1105 Many Triplets
ユーザー sgswsgsw
提出日時 2021-04-23 09:59:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 5,036 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,160 KB
実行使用メモリ 66,944 KB
最終ジャッジ日時 2024-07-04 06:59:16
合計ジャッジ時間 2,355 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
55,828 KB
testcase_01 AC 44 ms
56,048 KB
testcase_02 AC 44 ms
56,896 KB
testcase_03 AC 43 ms
56,132 KB
testcase_04 AC 43 ms
55,788 KB
testcase_05 AC 43 ms
56,952 KB
testcase_06 AC 45 ms
56,368 KB
testcase_07 AC 44 ms
55,448 KB
testcase_08 AC 44 ms
56,380 KB
testcase_09 AC 43 ms
56,416 KB
testcase_10 AC 56 ms
66,192 KB
testcase_11 AC 56 ms
65,664 KB
testcase_12 AC 55 ms
65,372 KB
testcase_13 AC 55 ms
66,308 KB
testcase_14 AC 56 ms
65,536 KB
testcase_15 AC 55 ms
65,924 KB
testcase_16 AC 56 ms
66,944 KB
testcase_17 AC 55 ms
66,060 KB
testcase_18 AC 55 ms
65,468 KB
testcase_19 AC 55 ms
65,076 KB
testcase_20 AC 43 ms
55,636 KB
testcase_21 AC 42 ms
55,180 KB
testcase_22 AC 42 ms
55,176 KB
testcase_23 AC 43 ms
55,612 KB
testcase_24 AC 43 ms
55,444 KB
testcase_25 AC 43 ms
55,772 KB
testcase_26 AC 43 ms
55,848 KB
testcase_27 AC 42 ms
56,052 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