[Python] ABC009 D

問題

D – 漸化式

スライド 56ページ以後

解けない…。

途中まで

まず、漸化式をそのままコードにしてみます。

入力例3はものすごく時間がかかります。

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

for _m in range(M-K):
    a_n_plus_k = 0
    for _k in range(K):
        tmp = C[_k] & A[_m + K - 1 -_k
        ]
        a_n_plus_k = tmp ^ a_n_plus_k
    A.append(a_n_plus_k)

print(a_n_plus_k)

スライドに従い、フィボナッチ数列を考えてみます。

まずはそのままコードにします。

N = 10
F = [0, 1]

for i in range(1, N-1):
    f_n_plus_2 = F[i] + F[i-1]
    F.append(f_n_plus_2)

print(F)

行列の累乗をかけるフィボナッチ数列の計算をコードにします。

隣接三項間漸化式と行列

import numpy as np

A = np.matrix([[1, 1],
               [1, 0]])

B = np.matrix([[1], 
               [0]])

N = 10

ans = A ** N * B

print(ans)

スライドに従い、行列の高速な累乗の計算を導入しコードにします。

import numpy as np

def power_matrix(a, n):
    """
    O(log n)
    """
    if n == 0:
        return np.eye(2)

    mat = power_matrix(a, n//2)
    mat = mat * mat

    if n & 1:
        return mat * a
    else:
        return mat

A = np.matrix([[1, 1],
               [1, 0]])

B = np.matrix([[1], 
               [0]])

N = 10

ans = power_matrix(A, N) * B

print(ans)

最終的には、以下のような回答に辿り着きたいんだけど、半環理解してから進みます。

https://atcoder.jp/contests/abc009/submissions/7803795