問題
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)
最終的には、以下のような回答に辿り着きたいんだけど、半環理解してから進みます。