在面试过程中，我遇到了以下问题：
从下面的谜题中，puzzle(power(2022, 100)) 的输出是什么？
function puzzle(N) {
A, B, C, D = 1, 1, 1, 1
.repeat N times {
X = D + 2 * C + 3 * B + 4 * A
a, b, c, d = b, c, d, x
}
return D % 10000000000
}
通过查看拼图并在我选择的语言上实现它，我发现它形成了某种斐波那契数列。但是，代码没有运行完，所以我无法找到输出。我回答说代码可以重构为 fibs 的总和来优化输出，但我做不到，但是，面试官说这是正确路径上的正确推理（他给了我更多时间来破解它，但我只是失败了）。
现在，我仍然对它感到好奇，即使在面试官失败之后。我能得到一些见解吗？
编辑：感谢接受的答案，我用 Python 破解了一个解决方案（除了答案更新中包含的那个），如果有人好奇，这里是代码：
#reimplemented in python because Ruby is a real pain to work with matrices
def matrix_pow(matrix, power, modulus):
# Initialize result to the identity matrix of the same size as matrix
result = [[int(i == j) for j in range(len(matrix))] for i in range(len(matrix))]
while power > 0:
# If the current bit of the exponent is 1, multiply result by matrix
if power % 2 == 1:
result = matrix_multiply(result, matrix, modulus)
# Square matrix and divide power by 2
matrix = matrix_multiply(matrix, matrix, modulus)
power //= 2
# Return the result
return result
# This function multiplies two matrices modulo a given modulus
def matrix_multiply(matrix1, matrix2, modulus):
# Initialize result to a matrix of the appropriate size filled with zeros
result = [[0] * len(matrix2[0]) for _ in range(len(matrix1))]
# Perform matrix multiplication
for i in range(len(matrix1)):
for j in range(len(matrix2[0])):
for k in range(len(matrix2)):
result[i][j] += matrix1[i][k] * matrix2[k][j]
result[i][j] %= modulus
# Return the result
return result
# This function solves the puzzle
def puzzle(n):
# Initialize matrix M
M = [[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[4, 3, 2, 1]]
# Calculate M^n modulo 10^10
M_pow = matrix_pow(M, n, 10**10)
# Initialize vector v
v = [1, 1, 1, 1]
# Multiply M^n by v to get the solution
result = matrix_multiply(M_pow, [[x] for x in v], 10**10)
# Return the element in the fourth row and first column of the result
return result[3][0]
print(puzzle(10))
# output 30520
print(puzzle(100))
# outputs 720820623
print(puzzle(2022**100))
# outputs 2436815984
我希望你知道什么是矩阵和矩阵乘法
在所有点上，拼图的状态都可以写成这样的列向量：
[A]
[B]
[C]
[D]
一步之后可以写成：
[B] [0 1 0 0] [A]
[C] -- [0 0 1 0] \/ [B]
[D] -- [0 0 0 1] /\ [C]
[X] [4 3 2 1] [D]
我们可以将右侧写为
M * vMv经过
NM^N * vvM^N为此，有一个窍门。制作系列
M, M^2, M^4, M^8, ...2022^100% 10000000000与 Fibonacci 的联系是它是由 2x2 转换矩阵计算的，您可以使用相同的逻辑。但我怀疑是否有办法从斐波那契到这个。
顺便说一句，我认为这是一个有趣的问题，但不是一个很好的面试问题。因为它测试的任意技能与您可能必须做的大多数编程工作没有很好的相关性。
这是 Python 版本。我验证了它与幂高达 100 的天真方法一致。
class ModuloValue:
def __init__ (self, n, m):
self.modulo = m
self.value = n % m
def __int__ (self):
return self.value
def __add__ (self, other):
return ModuloValue(self.value + int(other), self.modulo)
def __mul__ (self, other):
return ModuloValue(self.value * int(other), self.modulo)
def __str__ (self):
return str(self.value)
class Matrix:
def __init__ (self, rows):
self.rows = rows
def value (self, i, j):
return self.rows[i][j]
def __add__ (self, other):
rows1 = self.rows
rows2 = other.rows
rows_out = []
for i in range(len(rows1)):
row = []
for j in range(len(rows1[0])):
row.append(rows1[i][j] + rows2[i][j])
rows_out.append(row)
return Matrix(rows_out)
def __mul__ (self, other):
rows1 = self.rows
rows2 = other.rows
rows_out = []
for i in range(len(rows1)):
row = []
for k in range(len(rows2[0])):
value = rows1[i][0] * rows2[0][k]
for j in range(1, len(rows1[0])):
value = value + rows1[i][j] * rows2[j][k]
row.append(value)
rows_out.append(row)
return Matrix(rows_out)
def __str__ (self):
answer = '['
for row in self.rows:
answer += '\n [' + ', '.join((str(x) for x in row)) + ']'
return answer + '\n]'
def pow (self, n):
power = self
answer = None
while 0 < n:
if 1 == n % 2:
if answer is None:
answer = power
else:
answer = answer * power
power = power * power
n = n // 2
return answer
mod = 10000000000
rows = [
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[4, 3, 2, 1],
]
for i in range(len(rows)):
rows[i] = [ModuloValue(x, mod) for x in rows[i]]
m = Matrix(rows)
m_pow = m.pow(2022**100)
v = [[1], [1], [1], [1]]
print((m_pow * Matrix(v)).rows[3][0])