Проверьте сумму подмножества для специального уравнения массива

Question

Я пытался решить следующую проблему.

Нам даны N и A [0]

N <= 5000
A[0] <= 10^6 and even 
if i is odd then 
A[i] >= 3 * A[i-1]
if i is even
A[i]= 2 * A[i-1] + 3 * A[i-2]
element at odd index must be odd and at even it must be even.

Нам нужно минимизировать сумму массива.

и нам даны числа Q

 Q <= 1000
 X<= 10^18

Нам нужно определить, возможно ли получить сумму подмножества = X из нашего массива.

Что я пробовал,

Создать массив с минимальной суммой очень просто. Просто следуйте уравнениям и ограничениям.

Подход, который я знаю для subset-sum, - это динамическое программирование, которое имеет сложность по времени sum * sizeof (Array), но, поскольку sum может достигать 10 ^ 18, этот подход выиграл 't работа.

Есть ли какое-либо уравнение, которое я пропускаю?

Answer 1

Мы можем сделать это с небольшим количеством математики: извините за латекс. Я не уверен, что это возможно в стеке?

let X_n будет последовательность (такая же, как определенная вашим A)

Я предполагаю, что X_0 положительно.

Таким образом, последовательность строго увеличивается, и минимизация происходит, когда X_{2n+1} = 3X_{2n}

Мы можем вычислить общий член для X_{2n} и X_{2n+1}

v_0 = 
X0
X1

v_1 = 
X1
X2

отношение между v_0 и v_1 равно

M_a = 
0 1
3 2

отношение между v_1 и v_2 равно

M_b = 
0 1
0 3

следовательно, соотношение между v_2 и v_0 равно

M = M_bM_a = 
3 2
9 6

мы выводим

v_{2n} = 
X_{2n}
X_{2n+1}

v_{2n} = M^n v_0

Следуем классической диагонализации ... и мы (если не ошибаемся) получаем

X_{2n} = 9^n/3 X_0 + 2*9^{n-1}X_1
X_{2n+1} = 9^n X_0 + 2*9^{n-1}/3X_1

напомним, что X_1 = 3X_0 таким образом

X_{2n} = 9^n X_0
X_{2n+1} = 3.9^n X_0

Теперь, если мы представим сумму, которую мы хотим проверить в базе 9, мы получим

       9^{n+1}        9^n
___   ________  ___   ___
      X^{2n+2}        X^2n

В X^{2n}места, где мы можем поставить только 1 или 0 (это означает, что мы берем 2n-th элемент от A), мы можем также поставить 3 вместо места X^{2n}, что означает, что мы выбрали2n+1th элемент из массива

, поэтому нам просто нужно разложить число в базе 9 и проверить, все ли его цифры или 0,1 или 3 (а также, если его начальная цифра не являетсявне нашего массива ....)