温馨提示:本文翻译自stackoverflow.com,查看原文请点击:arrays - How to find the solution to dependent linear equations in constant time?

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

发布于 2020-03-27 11:24:28

这是我有一个示例问题:

Madhav参加了Riya的生日派对。他是一个极客,所以他不知道她想要哪种礼物。因此,他随身携带了一个整数数组。数组遵循特定顺序。数组的第一个元素为1。数组的第二个元素为6。数组的其他元素比前后数的平均值小2。很明显,Riya觉得这个想法很愚蠢,因此她想惩罚Madhav。她决定问Madhav数组的第n个数字。如果他说错了答案,她会打他一巴掌。帮助Madhav摆脱这种尴尬局面。

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
被浏览
124
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]

表示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)

进行编程时,请注意溢出!