結果

問題 No.541 3 x N グリッド上のサイクルの個数
ユーザー rpy3cpp
提出日時 2017-07-01 00:16:07
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 53 ms / 2,000 ms
コード長 4,059 bytes
コンパイル時間 127 ms
コンパイル使用メモリ 13,056 KB
実行使用メモリ 11,264 KB
最終ジャッジ日時 2024-10-04 22:11:09
合計ジャッジ時間 4,028 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

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))
0