ppc

CTFCup 2022 | Battles / Secondary | PPC

Название

optimization

Описание

Мы написали функцию, которая очень долго вычисляется. Ваша задача — оптимизировать её.

Раздатка

Участникам нужно выдать файлы:

• public/optimization.tar.gz

Деплой

Не требуется.

Решение

В задании дана функция, написанная на Python:

def func(init: int, k: int, mod: int) -> int:
    queue = collections.deque(
        [3, 1, 3, 3, 7, init],
    )

    for _ in range(k):
        value = sum(
            x * y for x, y in enumerate(queue)
        ) % mod

        queue.append(value)
        queue.popleft()

    return queue.pop()

Чтобы получить флаг, нужно вычислить func(1337, 10 ** 1000, 13 ** 37).

Изначальная функция func вычисляется за линейное от k время, поэтому дождаться 10 ** 1000 итераций цикла практически невозможно. Нужно заметить, что функция, на самом деле, вычисляет последовательность, задаваемую линейным рекуррентным соотношением:

F(i) = 0 * F(i-6) + 1 * F(i-5) + 2 * F(i-4) + 3 * F(i-3) + 4 * F(i-2) + 5 * F(i-1)

Нам нужно вычислить 10 ** 1000-ый элемент этой последовательности, при этом мы знаем первые 6 элементов. Вспомним, что линейные рекуррентные соотношения можно посчитать не за линейное, а за логарифмическое время, если воспользоваться матрицами:

1. построить матрицу, описывающую линейное рекуррентное соотношение

[0 0 0 0 0 0]
[1 0 0 0 0 1]
[0 1 0 0 0 2]
[0 0 1 0 0 3]
[0 0 0 1 0 4]
[0 0 0 0 1 5]

2. возвести эту матрицу в 10 ** 1000 степень, используя быстрый алгоритм

3. умножить вектор (3, 1, 3, 3, 7, init) на полученную матрицу

Таким образом мы сделаем log2(k) матричных умножений, не забывая после каждого умножения находить остаток от деления на mod.

Пример решения: solution/solver.py

Флаг

Cup{129866390023231817451786668553549832940001}