Как найти выход при использовании чрезвычайно большого входа в этом алгоритме?

Надеюсь, вы знаете, что такое матрицы и умножение матриц

Во всех точках состояние головоломки можно записать в виде вектора-столбца следующим образом:

[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 * v, где M — это матрица перехода 4x4, а v — вертикальный вектор.

После N шагов получаем M^N * v. Мы знаем наш начальный вектор v. И мы знаем, как подобрать ответ. Нам просто нужен хороший способ получить M^N.

И для этого, ну, есть хитрость. Озвучить сериал не сложно M, M^2, M^4, M^8, .... И с помощью этой серии и представления 2022^100 по основанию 2 вы можете найти ответ на загадку. К сожалению, цифры будут очень длинными. Но если вы сделаете все расчеты по модулю 10000000000 (это означает, что вы умножаете, а затем используете % 10000000000, чтобы получить остаток), то они остаются разумными, и вы можете получить ответ.

Связь с Фибоначчи заключается в том, что он вычисляется с помощью матрицы перехода 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])