如何在固定时间内求解相依线性方程组？

Question

这是我的一个示例问题：

马德哈夫去参加了里娅的生日聚会。他是个书呆子，所以他不知道她会喜欢哪种礼物。所以他随身携带了一个整数数组。数组遵循特定的顺序。数组的第一个元素是1。数组的第二个元素是6。数组的其他元素比它前面和后面的数字的平均值小两个。很明显，Riya觉得这个想法很愚蠢，因此她想惩罚Madhav。她决定向Madhav询问数组的第n个数字。如果他回答错了，她就会扇他耳光。帮助马德哈夫摆脱这种尴尬的境地。

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

输出：

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

约束：

1≤T≤105 1≤N≤1018

样本输入

2

1

3

样本输出

1

15

解释第一个测试用例是微不足道的，因为a 1 =1。在第二个测试用例中，a2=(a1+a3)/2-2。替换a 1和a2的值，我们得到: 6=(1+a2)/2-2。因此，a2=8*2-1=15

上述问题需要在固定的时间和空间内解决。如何找到这样的线性方程的第n个数，它从前2个固定数(这里是1，6)开始构建解？

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)

在对它进行编程时，请注意溢出！