白駿11444号:フィボナッチ数6

問題解決の考え方

行列の乗算を用いてフィボナッチ数

を求める

を使用して征服の繰返し二乗を分割する

✔概要
この問題を理解するためには,行列の乗算を用いてフィボナッチ数を求める方法を知る必要がある.
対角化でフィボナッチ数列を求める一般項:https://www.youtube.com/watch?v=uX2IsIykLJc
上記のビデオを学習し,実際の解題では対角化の概念を用いる必要はなく,以下の式のみを用いて解く.
この方法はn番目のフィボナッチ数を求める問題において,nが大きい場合に適している.

はまた,分割征服反復二乗を用いる必要があり,以前に解いた問題と同様である.https://velog.io/@dlehdtjq 00/伯準-1629回-乗算

✔完全コード

def matrixMultipli(row1, col1row2, col2, matrix1, matrix2):
    result = [[0 for _ in range(col2)] for _ in range(row1)]
    for i in range(row1):
        for j in range(col2):
            for k in range(col1row2):
                result[i][j] += matrix1[i][k] * matrix2[k][j]
            result[i][j] %= 1000000007

    return result


def devideConquer(n, matrix):
    if n == 1:
        return matrix
    tmp = devideConquer(n//2, matrix)
    if n % 2 == 0:
        return matrixMultipli(2, 2, 2, tmp, tmp)
    else:
        return matrixMultipli(2, 2, 2, matrixMultipli(2, 2, 2, tmp, tmp), matrix)


n = int(input())
A = [[1, 1], [1, 0]]

if n >= 3:
    result = matrixMultipli(2, 2, 1, devideConquer(n-1, A), [[1], [0]])
    print(result[0][0])  # 여기선 굳이 나머지 연산 필요 X (<-> 행렬제곱 문제)
else:
    print(1)

行列の乗算を実現

def matrixMultipli(row1, col1row2, col2, matrix1, matrix2):
    result = [[0 for _ in range(col2)] for _ in range(row1)]
    for i in range(row1):
        for j in range(col2):
            for k in range(col1row2):
                result[i][j] += matrix1[i][k] * matrix2[k][j]
            result[i][j] %= 1000000007

    return result

2つのマトリクスを乗算するために、マトリクス1のcolumnとマトリクス2のrowは同じでなければならない.また、乗算結果に対応する行列は、行列1の行と行列2の列とを有する.
行列の乗算により,上図のように三重for文を用いて実現すればよい.10,000,000,000,000,000,000,000で除算された残りの値を求めるため、%演算子を使用して2 D配列に入れます.

行列の積を用いてフィボナッチ数を求める

n = int(input())
A = [[1, 1], [1, 0]]
result = matrixMultipli(2, 2, 1, devideConquer(n-1, A), [[1], [0]])

print(result[0][0])  # 여기선 굳이 나머지 연산 필요 X (<-> 행렬제곱 문제)

以上の式から,n番目のフィボナッチ数,すなわちF nを求めるためには,[[1,1],[1,0]行列にn−1次方程式を乗じる必要があることが分かる.また、その結果に[1],[0]を乗じなければならない.
そこで,まずDevideConquer関数を用いてA行列をn−1反復(以下,パーティション征服の実装について論じる)し,次に[1],[0]行列を乗じる.
演算の結果行列では,F nはrow 0,column 0にあり,結果[0][0]を出力すればよい.コード全体のように、n<3であれば、単独で処理することも忘れないでください.

パーティション征服

を実施

def devideConquer(n, matrix):
    if n == 1:
        return matrix
    tmp = devideConquer(n//2, matrix)
    if n % 2 == 0:
        return matrixMultipli(2, 2, 2, tmp, tmp)
    else:
        return matrixMultipli(2, 2, 2, matrixMultipli(2, 2, 2, tmp, tmp), matrix)

再帰的に自分を呼び出し,n回にマトリクスを乗じた関数.直接実現した行列の乗算関数のみを用いたため,構造自体は以前に解いた問題と同じであるため,説明を省略する.