結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー rpy3cpprpy3cpp
提出日時 2015-08-20 00:27:13
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 469 ms / 5,000 ms
コード長 3,922 bytes
コンパイル時間 86 ms
コンパイル使用メモリ 13,184 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-07-18 10:46:37
合計ジャッジ時間 7,635 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
11,264 KB
testcase_01 AC 34 ms
11,264 KB
testcase_02 AC 281 ms
11,264 KB
testcase_03 AC 56 ms
11,136 KB
testcase_04 AC 126 ms
11,264 KB
testcase_05 AC 111 ms
11,264 KB
testcase_06 AC 127 ms
11,264 KB
testcase_07 AC 188 ms
11,264 KB
testcase_08 AC 49 ms
11,264 KB
testcase_09 AC 150 ms
11,264 KB
testcase_10 AC 78 ms
11,392 KB
testcase_11 AC 82 ms
11,264 KB
testcase_12 AC 113 ms
11,264 KB
testcase_13 AC 64 ms
11,264 KB
testcase_14 AC 40 ms
11,264 KB
testcase_15 AC 220 ms
11,264 KB
testcase_16 AC 192 ms
11,264 KB
testcase_17 AC 77 ms
11,264 KB
testcase_18 AC 199 ms
11,264 KB
testcase_19 AC 265 ms
11,264 KB
testcase_20 AC 223 ms
11,264 KB
testcase_21 AC 469 ms
11,776 KB
testcase_22 AC 388 ms
11,392 KB
testcase_23 AC 47 ms
11,648 KB
testcase_24 AC 231 ms
11,520 KB
testcase_25 AC 216 ms
11,392 KB
testcase_26 AC 209 ms
11,648 KB
testcase_27 AC 251 ms
11,264 KB
testcase_28 AC 80 ms
11,392 KB
testcase_29 AC 423 ms
11,264 KB
testcase_30 AC 269 ms
11,264 KB
testcase_31 AC 32 ms
11,136 KB
testcase_32 AC 103 ms
11,264 KB
testcase_33 AC 136 ms
11,264 KB
testcase_34 AC 116 ms
11,136 KB
testcase_35 AC 101 ms
11,264 KB
testcase_36 AC 212 ms
11,264 KB
testcase_37 AC 49 ms
11,264 KB
testcase_38 AC 236 ms
11,264 KB
testcase_39 AC 115 ms
11,264 KB
権限があれば一括ダウンロードができます

ソースコード

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])) + sum(As[:-1])) % mod
    
    return fk, sk


def inverse(n):
    mod = 10 ** 9 + 7
    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
    q = mod - 2
    minv = 1
    while q:
        if q & 1:
            minv *= m
            minv %= mod
        m *= m
        m %= mod
        q >>= 1
    for row in data:
        for i in range(n):
            row[i] *= minv
            row[i] %= mod
    return Matrix().from2Dlist(data)


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