結果

問題 No.492 IOI数列
コンテスト
ユーザー rpy3cpp
提出日時 2017-03-26 17:32:31
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 29 ms / 1,000 ms
コード長 4,392 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 13,312 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2024-07-06 06:31:07
合計ジャッジ時間 1,471 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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 = 0):
        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 pow(self, n, modulo = 0):
        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))

N = int(input())

def solve(N):
    mod = 10**9 + 7
    a = solve_core(N, mod)
    if N % 11:
        b = '10' * ((N % 11) - 1) + '1'
    else:
        b = 0
    return a, b

def solve_core(N, mod):
    '''a[1] = 1, a[n+1] = 100*a[n] + 1 のとき、a[N] % mod を求める。
    A = [[100, 1],
         [  0, 1]]
    とすると、a[n] = A**n @ [[0], [1]]
    '''
    A = Matrix().from2Dlist([[100, 1], [0, 1]])
    An = pow(A, N, mod)
    return An[0][1]

a, b = solve(N)
print(a)
print(b)
0