algorithm arrays data-structures math

# arrays - 如何在恒定时间内找到相关线性方程的解？

Input : First line contains T , number of test cases and the next T lines contain N , the Nth element of the above array to be found.

Output:

For each test case, output an integer which is the Nth number of the array. As the answer can be very large, output it modulo 109+7

Constraints:

1 ≤ T ≤ 105 1 ≤ N ≤ 1018

SAMPLE INPUT

2

1

3

SAMPLE OUTPUT

1

15

Explanation First test case is trivial as a [1] = 1. In second test case, a[2]=(a[1]+a[3])/2-2. Substituting the values of a [1] and a[2] , we get: 6=(1+a[2])/2-2. So, a[2]=8*2-1=15

The above question needs to be solved in constant time and space . How to find the nth number of such linear equations which goes on building solution from first 2 fixed numbers ( 1 , 6 here ) ?

Natesh bhat

181
Damien 2019-07-04 00:18

The equation corresponds to

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

This can be rewritten as

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

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

``````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)
``````