行列累乗
/icons/hr.icon
#典型 #数学
※個人的なメモが大半です
/icons/hr.icon
フィボナッチ数列の行列累乗
計算量は $ O(\log N)
繰り返し二乗法を使用して高速化
code:Fibonacci.py
def matrix_multi(a: list, b: list) -> list:
len_a, len_b, len_b_zero = len(a), len(b), len(b0)
c = [0 * len(b0) for _ in range(len_a)]
for i in range(len_a):
for j in range(len_b_zero):
for k in range(len_b):
cij += aik * bkj
cij %= mod
return c
def matrix_pow(a: list, n: int) -> list:
len_a = len(a)
cnt = [0 * len_a for _ in range(len_a)]
for i in range(len_a):
cntii = 1
while n > 0:
if n & 1:
cnt = matrix_multi(a, cnt)
a = matrix_multi(a, a)
n >>= 1
return cnt
n = int(input())
mod = 998244353
fibonacci = 1, 1], [1, 0
fibonacci = matrix_pow(fibonacci, n)
ans = fibonacci10
# print(*fibonacci, sep="\n")
print(ans)
/icons/hr.icon
類題
類題１
AtCoder Beginner Contest 009-D - 漸化式
考察・解説
問題文の長い式を漸化式として表すと以下のようになる
$ A[i] = (C[1] \land A[i - 1]) \land (C[2] \& A[i - 2]) \oplus ... \oplus (C[K] \& A[i - K])
※$ i := N + K
求めたい数は第 $ M 項で、愚直に各項に関してやると $ O(K) かかるので $ O(KM)
第 $ i 項に必要なものは $ i - 1 項以下の数なので、漸化式に帰着できると考える
code:Python
def matrix_multi(a: list, b: list) -> list:
len_a, len_b, len_b_zero = len(a), len(b), len(b0)
c = [0 * len(b0) for _ in range(len_a)]
for i in range(len_a):
for j in range(len_b_zero):
for k in range(len_b):
cij ^= aik & bkj
return c
def matrix_pow(matrix: list, k: list):
cnt = [0 * len(matrix) for _ in range(len(matrix))]
if k == 0:
for i in range(len(matrix)):
for j in range(len(matrix)):
if i == j:
cntij = INF
return cnt
if k & 1:
return matrix_multi(matrix_pow(matrix, k - 1), matrix)
return matrix_pow(matrix_multi(matrix, matrix), k >> 1)
k, m = map(int, input().split())
a = list(map(int, input().split()))
c = list(map(int, input().split()))
INF = 2 ** 35 - 1
if m <= k:
print(am - 1)
exit()
matrix = [0 * k for _ in range(k)]
for i in range(k):
matrix0i = ci
if i != 0:
matrixii - 1 = INF
b = matrix_pow(matrix, m - k)
v = a[-1 - i + 0 * (k - 1) for i in range(k)]
ans = matrix_multi(b, v)
print(ans00)
/icons/hr.icon