2D DP с большими размерами

Question

Учитывая n + 1-кортеж (a ₀ , a ₁ , ..., a _n ).

Мы нужно вычислить F (m, n).

Дано:

a ₀ <= a <sub>1 <= ... <= a <sub>n

F (x, y) = a _y * F (x - 1, y) + F (x, y - 1)

F (0, y) = 1 для всех y

F (x, 0) = a ₀ ^x

Я думал из-за подхода dp, но проблема, с которой я столкнулся, слишком велика 'm', которая может превышать миллиард.

Есть ли способ решить эту проблему?

Я чувствую, что это можно преобразовать в проблема возведения в матрицу, но не могу понять, как?

Я новичок в переполнении стека и программировании. Будем благодарны за любые предложения по редактированию и подход / решение проблемы.

Answer 1

Ваша идея "матричного возведения в степень" верна.

Напишите F(x, _) как вертикальный вектор. (То есть одна запись для каждого значения y.)

Существует матрица A такая, что F(x+1, _) = A * F(x, _). Оказавшись, получается, что F(x+k, _) = A^k * F(x, _).

Теперь вы знаете F(0, _). Вы можете найти A. Затем с помощью повторного возведения в квадрат вы можете найти A^m и теперь вы можете ответить на ваш вопрос.