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

Question

这是我的一个示例问题:

Madhav 去了 Riya 的生日派对。他是个极客，所以他不知道她喜欢什么礼物。所以他带了一个整数数组。该阵列遵循特定的顺序。数组的第一个元素是 1。数组的第二个元素是 6。数组的其他元素比它前面和后面的数字的平均值小两个。很明显，Riya 觉得这个想法很愚蠢，因此她想惩罚 Madhav。她决定向 Madhav 询问阵列的第 n 个数字。如果他回答错了，她就会扇他耳光。帮助 Madhav 摆脱这种尴尬的境地。

输入:第一行包含 T，测试用例的数量，接下来的 T 行包含 N，即要找到的上述数组的第 N 个元素。

输出:

对于每个测试用例，输出一个整数，它是数组的第 N 个数。由于答案可能非常大，输出它模 109+7

约束:

1≤T≤1051≤N≤1018

样本输入

2

1

3

样本输出

1

15

解释第一个测试用例很简单，因为 a [1] = 1。在第二个测试用例中，a[2]=(a[1]+a[3])/2-2。代入 a [1] 和 a[2] 的值，我们得到:6=(1+a[2])/2-2。所以，a[2]=8*2-1=15

上述问题需要在恒定的时空条件下求解。如何从前 2 个固定数(这里是 1 、 6 )找到第 n 个这样的线性方程组来构建解？

Answer 1

等式对应

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)

编程时，注意溢出!