結果

問題 No.194 フィボナッチ数列の理解(1)
ユーザー rpy3cpprpy3cpp
提出日時 2015-08-20 00:27:13
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
AC  
実行時間 337 ms / 5,000 ms
コード長 3,922 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 11,296 KB
実行使用メモリ 9,096 KB
最終ジャッジ日時 2023-09-25 13:42:34
合計ジャッジ時間 6,878 ms
ジャッジサーバーID
(参考情報)
judge11 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
8,800 KB
testcase_01 AC 18 ms
8,812 KB
testcase_02 AC 220 ms
8,840 KB
testcase_03 AC 38 ms
8,724 KB
testcase_04 AC 96 ms
8,348 KB
testcase_05 AC 81 ms
8,764 KB
testcase_06 AC 96 ms
8,744 KB
testcase_07 AC 144 ms
8,852 KB
testcase_08 AC 33 ms
8,676 KB
testcase_09 AC 113 ms
8,492 KB
testcase_10 AC 55 ms
8,644 KB
testcase_11 AC 57 ms
8,672 KB
testcase_12 AC 81 ms
8,700 KB
testcase_13 AC 44 ms
8,448 KB
testcase_14 AC 24 ms
8,660 KB
testcase_15 AC 170 ms
8,908 KB
testcase_16 AC 147 ms
8,912 KB
testcase_17 AC 53 ms
8,636 KB
testcase_18 AC 154 ms
8,896 KB
testcase_19 AC 204 ms
8,880 KB
testcase_20 AC 189 ms
8,752 KB
testcase_21 AC 337 ms
9,000 KB
testcase_22 AC 293 ms
8,704 KB
testcase_23 AC 30 ms
9,024 KB
testcase_24 AC 169 ms
9,096 KB
testcase_25 AC 157 ms
8,940 KB
testcase_26 AC 150 ms
9,096 KB
testcase_27 AC 180 ms
8,456 KB
testcase_28 AC 55 ms
8,928 KB
testcase_29 AC 307 ms
8,624 KB
testcase_30 AC 208 ms
8,800 KB
testcase_31 AC 18 ms
8,736 KB
testcase_32 AC 75 ms
8,752 KB
testcase_33 AC 103 ms
8,784 KB
testcase_34 AC 87 ms
8,696 KB
testcase_35 AC 77 ms
8,720 KB
testcase_36 AC 165 ms
8,960 KB
testcase_37 AC 32 ms
8,676 KB
testcase_38 AC 182 ms
8,800 KB
testcase_39 AC 84 ms
8,724 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