这是我有一个示例问题:
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 ) ?
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)
进行编程时,请注意溢出!
请解释您如何使用a [1] = 1,a [2] = 6编写a [n] = a [n-1] + 4(n-1)+1,以及u如何将大表达式简化为a [n] = n(2n-1)
@Nateshbhat我尝试完成一点。希望现在更清楚