結果

問題 No.194 フィボナッチ数列の理解(1)
コンテスト
ユーザー titia
提出日時 2026-03-11 07:12:02
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 93 ms / 5,000 ms
コード長 1,434 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 209 ms
コンパイル使用メモリ 85,344 KB
実行使用メモリ 215,132 KB
最終ジャッジ日時 2026-03-11 07:12:06
合計ジャッジ時間 3,206 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

mod=10**9+7

def prod(A,B,k,l,m):# A:k*l,B:l*m
    C=[[None for i in range(m)] for j in range(k)]

    for i in range(k):
        for j in range(m):
            ANS=0
            for pl in range(l):
                ANS=(ANS+A[i][pl]*B[pl][j])%mod

            C[i][j]=ANS

    return C

def plus(A,B,k,l):# a,B:k*l
    C=[[None for i in range(l)] for j in range(k)]

    for i in range(k):
        for j in range(l):
            C[i][j]=(A[i][j]+B[i][j])%mod

    return C


N,K=list(map(int,input().split()))
A=list(map(int,input().split()))

if K>1000000:
    X=[[0]*(N+1) for i in range(N+1)]

    for i in range(N-1):
        X[i+1][i]=1

    for i in range(N+1):
        X[i][-1]=1

    for i in range(N):
        X[i][-2]=1

    #for x in X:
    #    print(*x)

    POWA=[X]

    # 漸化式を行列累乗で求める（ダブリング）

    for i in range(60):
        POWA.append(prod(POWA[-1],POWA[-1],N+1,N+1,N+1)) # ベキを求めて

    X=A[:]
    X.append(sum(A)%mod)

    #print(X)

    X=[X]

    K=K-N

    while K:
        X=prod(X,POWA[K.bit_length()-1],1,N+1,N+1) # n乗の場合
        K-=1<<(K.bit_length()-1)

    #print(X)

    print(X[0][-2]%mod,X[0][-1]%mod)
    

else:
    S=[0]
    for a in A:
        S.append((S[-1]+a)%mod)

    for i in range(K-N):
        A.append(S[-1]-S[-N-1])
        S.append((S[-1]+A[-1])%mod)

    print(A[-1]%mod,S[-1]%mod)
0