Как решить проблему суммы подмножеств с большой суммой 10 ^ 18 с рекуррентным отношением в качестве элементов массива

Question

Постановка задачи

Вам задано N, размер массива A и A0, первый элемент массива.Другие элементы массива можно рассчитать по формуле:

• A [i]> = 3 * A [i-1], если i нечетное

• A [i] = 2 * A [i-1] + 3 * A [i-2], если i четное

i варьируется от 1 до N -1

Массив следует за специальной собственностью. Элементы в четных индексах массива четны, а элементы в нечетных индексах массива нечетны .Ваша первая задача - подготовить этот массив так, чтобы сумма массива была минимизирована, а массив соответствовал всем заданным условиям.Вам дано Q запросов.Каждый запрос состоит из одного целого числа X. Вы должны вывести true, если мы можем достичь этого, добавив некоторые элементы массива A, false, если это невозможно.

Ограничения

• 1 <= T <= 50 </li>
• 1 <= N <= 5000 </li>
• 1 <= A0 <= 10 ^ 6 </li>
• A0 чётно
• 1 <= Q <= 1000 </li>
• 1 <= X <= 10 ^ 18 </li>

Образец теста

Ввод

1
4 2
5
3 27 36 68 88

Вывод

false
true
false
true
true

Объяснение - Элементы массива [2,7,20,61]

Я пробовал наивный и дп подход, но получил Превышение лимита памяти.

Answer 1

A[i] >= 3*A[i-1] , if i is odd

Исправление, когда i нечетное, это умножение, а не сложение

Ключевые моменты:

1. В массиве будет не так много записей до 10 ^ 18, потому что каждыйвремя, которое мы умножаем на некоторое число для следующего числа
2. X меньше 10 ^ 18, поэтому игнорируйте числа больше 10 ^ 18 в массиве A, всякий раз, когда происходит первое переполнение, прекратите вычислять A [i]

3. A [i] больше, чем сумма всех элементов с индексами меньше i

   A[i] > A[i-1]+A[i-2]......A[0]
   

Теперь начинаетсярешение
Для каждого заданного X, K - это размер массива A, имеющего числа в порядке возрастания, где A [i] <= 10 ^ 18 </p>

for(i=k;i>=0;i--)
{
    if(X>=A[i])
    X-=A[i];
}

if(X==0)
    cout<<"true\n";
else
    cout<<"false\n";