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

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
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))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX