时间戳

首页 > 解决方案 > 如何在恒定时间内找到相关线性方程组的解？

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

问题描述

这是我的一个示例问题：

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

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

输出：

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

约束：

1 ≤ T ≤ 105 1 ≤ 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 个这样的线性方程组？

标签： arraysalgorithmmathdata-structures

解决方案

方程对应于

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)

编程时注意溢出！

推荐阅读