Как найти решение зависимых линейных уравнений за постоянное время? - PullRequest
Новая
       33

Как найти решение зависимых линейных уравнений за постоянное время?

0 голосов
/ 03 июля 2019

Вот типовой вопрос, который у меня есть:

Мадхав пошел на день рождения Рии. Он был фанатом, поэтому он понятия не имел, какой подарок ей понравится. Поэтому он взял с собой массив целых чисел. Массив следовал определенному порядку. Первый элемент массива - 1. Второй элемент массива - 6. Другие элементы массива на два меньше среднего числа, предшествующего и следующего за ним. Как очевидно, Рия чувствовала, что эта идея была глупой, и поэтому она хотела наказать Мадхава. Она решила спросить у Мадхава n-й номер массива. Если он скажет неправильный ответ, она даст ему пощечину. Помогите Мадхаву сбежать из этой неловкой ситуации.

Входные данные: первая строка содержит T, количество тестов и следующие T строк содержат N, N-й элемент указанного выше массива.

Выход:

Для каждого теста выведите целое число, которое является N-м числом массива. Поскольку ответ может быть очень большим, выведите его по модулю 109 + 7

Ограничения:

1 ≤ T ≤ 105 1 ≤ N ≤ 1018

ОБРАЗЕЦ ВХОДА

2

1

3

ОБРАЗЕЦ ВЫХОДА

1

15

Пояснение Первый тестовый случай тривиален, так как [1] ​​= 1. Во втором тестовом примере a [2] = (a [1] + a [3]) / 2-2. Подставляя значения a [1] и a [2], получим: 6 = (1 + a [2]) / 2-2. Итак, [2] = 8 * 2-1 = 15

Вышеуказанный вопрос необходимо решать в постоянном времени и пространстве. Как найти n-е число таких линейных уравнений, которое идет на построение решения из первых 2 фиксированных чисел (1, 6 здесь)?

1 Ответ

1 голос
/ 03 июля 2019

Уравнение соответствует 

a[n] = (a[n-1] + a[n+1])/2 - 2

Это можно переписать как 

a[n+1] = 2(a[n]+2) - a[n-1]

Выражение a[n] = a[n-1] + b[n] и вычисление первых значений b[n]: 

b[1] = 1; b[2] = 5; b[3] = 9; b[4] = 13; b[5] = 17; etc.

Легко видеть, что b[n] = 4(n-1) + 1

Эту общую формулу можно проверить по индукции. Тогда следует, что 

a[n] = a[n-1] + 4(n-1) + 1

А потом 

a[n] = 4(n-1) + 1  
     + 4(n-2) + 1  
     + 4(n-3) + 1  
     + ...  
     + 1

Наконец, используя это 

sum_(i=0)^(n-1) (i) = n(n-1)/2

Мы можем сделать вывод, что 

a[n] = 2n(n-1) + 4n = n(2n-1)

При программировании обратите внимание на переполнение!

...