#185497 (Python3) No.541 3 x N グリッド上のサイクルの個数

提出ソース

結果

問題	No.541 3 x N グリッド上のサイクルの個数
ユーザー	rpy3cpp
提出日時	2017-07-01 00:16:07
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	54 ms / 2,000 ms
コード長	4,059 bytes
コンパイル時間	124 ms
コンパイル使用メモリ	13,312 KB
実行使用メモリ	11,392 KB
最終ジャッジ日時	2024-04-15 07:21:13
合計ジャッジ時間	4,355 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	33 ms 11,264 KB
testcase_01	AC	35 ms 11,264 KB
testcase_02	AC	36 ms 11,392 KB
testcase_03	AC	33 ms 11,264 KB
testcase_04	AC	33 ms 11,264 KB
testcase_05	AC	33 ms 11,392 KB
testcase_06	AC	33 ms 11,264 KB
testcase_07	AC	34 ms 11,392 KB
testcase_08	AC	33 ms 11,264 KB
testcase_09	AC	43 ms 11,264 KB
testcase_10	AC	41 ms 11,264 KB
testcase_11	AC	42 ms 11,264 KB
testcase_12	AC	42 ms 11,264 KB
testcase_13	AC	41 ms 11,264 KB
testcase_14	AC	41 ms 11,392 KB
testcase_15	AC	42 ms 11,264 KB
testcase_16	AC	42 ms 11,264 KB
testcase_17	AC	43 ms 11,264 KB
testcase_18	AC	42 ms 11,264 KB
testcase_19	AC	53 ms 11,264 KB
testcase_20	AC	54 ms 11,264 KB
testcase_21	AC	53 ms 11,264 KB
testcase_22	AC	52 ms 11,264 KB
testcase_23	AC	53 ms 11,392 KB
testcase_24	AC	52 ms 11,392 KB
testcase_25	AC	53 ms 11,392 KB
testcase_26	AC	53 ms 11,264 KB
testcase_27	AC	54 ms 11,392 KB
testcase_28	AC	53 ms 11,264 KB
testcase_29	AC	34 ms 11,264 KB
testcase_30	AC	35 ms 11,264 KB
testcase_31	AC	33 ms 11,264 KB
testcase_32	AC	34 ms 11,264 KB
testcase_33	AC	33 ms 11,264 KB
testcase_34	AC	33 ms 11,392 KB
testcase_35	AC	34 ms 11,264 KB
testcase_36	AC	34 ms 11,264 KB
testcase_37	AC	34 ms 11,264 KB
testcase_38	AC	35 ms 11,264 KB
testcase_39	AC	34 ms 11,264 KB
testcase_40	AC	42 ms 11,264 KB
testcase_41	AC	41 ms 11,264 KB
testcase_42	AC	43 ms 11,264 KB
testcase_43	AC	43 ms 11,264 KB
testcase_44	AC	43 ms 11,264 KB
testcase_45	AC	43 ms 11,264 KB
testcase_46	AC	43 ms 11,392 KB
testcase_47	AC	42 ms 11,264 KB
testcase_48	AC	41 ms 11,264 KB
testcase_49	AC	41 ms 11,264 KB
testcase_50	AC	42 ms 11,264 KB
testcase_51	AC	53 ms 11,264 KB
testcase_52	AC	52 ms 11,264 KB
testcase_53	AC	53 ms 11,264 KB
testcase_54	AC	53 ms 11,264 KB
testcase_55	AC	52 ms 11,264 KB
testcase_56	AC	52 ms 11,264 KB
testcase_57	AC	53 ms 11,392 KB
testcase_58	AC	53 ms 11,264 KB
testcase_59	AC	52 ms 11,392 KB
testcase_60	AC	53 ms 11,264 KB
testcase_61	AC	54 ms 11,392 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

class Matrix(object):
    def __init__(self, nrow=1, ncol=1):
        self.nrow = nrow
        self.ncol = ncol
        self._data = [[0] * nrow for c in range(ncol)]

    def from2Dlist(self, data, shallow_copy=False):
        self.nrow = len(data)
        self.ncol = len(data[0])
        for row in data:
            if len(row) != self.ncol:
                raise IndexError('All column lengths must be same.')
        if shallow_copy:
            self._data = data
        else:
            self._data = [row[:] for row in data]
        return self

    def makeIdentityMatrix(self, n):
        self.nrow = n
        self.ncol = n
        self._data = [[0] * n for c in range(n)]
        for i in range(n):
            self._data[i][i] = 1
        return self

    def __getitem__(self, key):
        if isinstance(key, int):
            return self._data[key]
        row, col = key
        return self._data[row][col]

    def __setitem__(self, key, value):
        if isinstance(key, int):
            if len(value) == self.ncol:
                self._data[key] = value[:]
            else:
                raise IndexError('The length of value must be equal to ncol.')
        else:
            row, col = key
            self._data[row][col] = value

    def __mod__(self, modulo):
        mat = [[c % modulo for c in row] for row in self._data]
        return Matrix().from2Dlist(mat, shallow_copy=True)

    def __imod__(self, modulo):
        for row in self._data:
            for i in range(self.ncol):
                row[i] %= modulo
        return self

    def __add__(self, other):
        if self.nrow != other.nrow or self.ncol != other.ncol:
            raise TypeError('lhs and rhs must be same size.')
        mat = []
        for row1, row2 in zip(self._data, other._data):
            row = [a + b for a, b in zip(row1, row2)]
            mat.append(row)
        return Matrix().from2Dlist(mat, shallow_copy=True)

    def __sub__(self, other):
        if self.nrow != other.nrow or self.ncol != other.ncol:
            raise TypeError('lhs and rhs must be same size.')
        mat = []
        for row1, row2 in zip(self._data, other._data):
            row = [a - b for a, b in zip(row1, row2)]
            mat.append(row)
        return Matrix().from2Dlist(mat, shallow_copy=True)

    def __matmul__(self, other):
        if self.ncol != other.nrow:
            raise TypeError('ncol of lhs and nrow of rhs must be same.')
        mat = []
        mat2 = other._data
        n = other.ncol
        for row1 in self._data:
            row = [sum(a * b[i] for a, b in zip(row1, mat2)) for i in range(n)]
            mat.append(row)
        return Matrix().from2Dlist(mat, shallow_copy=True)
        
    def __pow__(self, n, modulo = 10**9+7):
        if self.ncol != self.nrow:
            raise TypeError('operator pow (**) is not supproted when ncol != nrow.')
        mat = Matrix().from2Dlist(self._data)
        if modulo: mat %= modulo
        mat2 = Matrix().makeIdentityMatrix(self.ncol)
        while n:
            if n & 1:
                mat2 @= mat
                if modulo: mat2 %= modulo
            mat @= mat
            if modulo: mat %= modulo
            n >>= 1
        return mat2

    def __imatmul__(self, other):
        self = self.__matmul__(other)
        return self

    def __str__(self):
        return '\n'.join(map(str, self._data))


def solve(N):
    mat = [[1,0,0,0,0,0,0,0,0,0],
           [0,1,1,1,1,1,0,1,1,1],
           [1,0,1,0,1,0,0,1,0,1],
           [1,0,0,1,1,0,0,0,1,1],
           [1,0,1,1,1,0,0,0,1,1],
           [1,0,0,0,0,1,0,1,1,1],
           [1,0,1,0,0,1,1,0,0,0],
           [0,0,0,0,0,0,0,1,0,1],
           [1,0,0,1,1,1,0,0,1,1],
           [1,0,1,1,1,1,1,0,1,1]]
    mat1 = Matrix().from2Dlist(mat)
    v0 = Matrix().from2Dlist([[1],[0],[1],[1],[1],[1],[1],[0],[1],[1]])
    vf = Matrix().from2Dlist([[0,1,1,1,1,1,0,1,1,1]])
    mod = 10**9 + 7
    matN = mat1**(N - 1)
    vN = matN @ v0
    ans = vf @ vN
    return ans[0][0] % mod

N = int(input())
print(solve(N))

yukicoder

結果

テストケース

ソースコード