結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー rpy3cpprpy3cpp
提出日時 2015-08-19 23:58:46
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 3,800 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 11,264 KB
実行使用メモリ 9,196 KB
最終ジャッジ日時 2023-09-25 13:39:45
合計ジャッジ時間 6,808 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
8,692 KB
testcase_01 AC 18 ms
8,716 KB
testcase_02 AC 218 ms
8,776 KB
testcase_03 AC 37 ms
8,612 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 188 ms
8,704 KB
testcase_21 AC 334 ms
9,196 KB
testcase_22 AC 290 ms
8,664 KB
testcase_23 AC 29 ms
9,136 KB
testcase_24 AC 168 ms
9,004 KB
testcase_25 AC 155 ms
8,960 KB
testcase_26 AC 152 ms
9,116 KB
testcase_27 AC 180 ms
8,652 KB
testcase_28 AC 55 ms
8,804 KB
testcase_29 AC 309 ms
8,644 KB
testcase_30 WA -
testcase_31 AC 18 ms
8,588 KB
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
権限があれば一括ダウンロードができます

ソースコード

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):
        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.')
        self._data = [[val for val in row] for row in data]
        return self

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

    def __setitem__(self, key, value):
        row, col = key
        self._data[row][col] = value

    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)

    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)

    def __mul__(self, other):
        '''行列の積を求める。要素毎の乗算ではない。
        '''
        mod = 10 ** 9 + 7
        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)) % mod for i in range(n)]
            mat.append(row)
        return Matrix().from2Dlist(mat)

    def __imul__(self, other):
        self = self.__mul__(other)
        return self

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


def read_data():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    return N, K, As


def solve(N, K, As):
    if K <= 10**6:
        return solve2(N, K, As)
    else:
        return solve3(N, K, As)


def solve2(N, K, As):
    mod = 10**9 + 7
    As.append(sum(As) % mod)
    idx = N
    cum = sum(As) % mod
    for i in range(1, K - N):
        new_idx = (idx + 1) % (N + 1)
        As[new_idx] = (2 * As[idx] - As[new_idx]) % mod
        cum += As[new_idx]
        cum %= mod
        idx = new_idx
    return As[idx], cum


def solve3(N, K, As):
    mod = 10 ** 9 + 7
    if K <= N:
        return As[K - 1]
    data = [[1] * N]
    for n in range(N-1):
        row = [0] * N
        row[n] = 1
        data.append(row)
    dataI = [[0] * N for i in range(N)]
    for n in range(N):
        dataI[n][n] = 1
    mat = Matrix().from2Dlist(data)
    mat2 = Matrix().from2Dlist(dataI)
    K = K - N
    while K:
        if K & 1:
            mat2 *= mat
        mat *= mat
        K >>= 1
    fk = sum(mat2[0, i] * ai for i, ai in enumerate(As[::-1])) % mod

    mat = Matrix().from2Dlist(data)
    matI = Matrix().from2Dlist(dataI)
    mat3 = mat2 * mat - matI
    inv = inverse(N)
    inv *= mat3
    sk = (sum(inv[0, i] * ai for i, ai in enumerate(As[::-1]))//(N - 1) + sum(As[:-1])) % mod
    
    return fk, sk


def inverse(n):
    '''
    1/5(1,5, 4, 3, 2, 1)
   (1,0, 4, 3, 2, 1)
   (1,0,-1, 3, 2, 1)
   (1,0,-1,-2, 2, 1)
   (1,0,-1,-2,-3, 1)
   (1,0,-1,-2,-3,-4)
    '''
    row = [i for i in range(N, 0, -1)]
    data = [row[:] for i in range(n)]
    m = n - 1
    for i in range(n):
        for j in range(i + 1):
            data[i][j] -= m
    return Matrix().from2Dlist(data)


N, K, As = read_data()
print(*solve(N, K, As))
0