結果

問題 No.194 フィボナッチ数列の理解(1)
コンテスト
ユーザー rpy3cpp
提出日時 2015-08-19 23:58:46
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,800 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 13,184 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2024-07-18 10:44:13
合計ジャッジ時間 7,782 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 WA * 25
権限があれば一括ダウンロードができます

ソースコード

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