Google Code Jam 2008:第1A轮问题3

Question

在Google Code Jam 2008第1A轮中,存在以下问题:

计算数字小数点前的最后三位数(3 + sqrt(5))^ n

n可以是大数量最多为1000000.
例如:如果n = 2,则(3 + SQRT(5))^ 2 = 27 0.4164079 ...答案是027
对于n = 3:(3 + SQRT(5) )^ 3 = 3 935 .73982 ...答案是935.

解决方案之一是创建矩阵M 2x2:[[0,1],[ - 4],6],而不是计算矩阵P = M ^ n,其中计算由模1000执行,结果是(6*P[0,0] + 28*P[0,1] - 1)mod 1000.

谁能解释一下这个解决方案？

Answer 1

我将提出一种解决这个问题的方法,甚至不需要理解解决方案.

假设您熟悉斐波那契数:

ghci> let fib = 0 : 1 : zipWith (+) fib (tail fib)
ghci> take 16 fib
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]

并熟悉其封闭形式表达:

ghci> let calcFib i = round (((1 + sqrt 5) / 2) ^ i / sqrt 5)
ghci> map calcFib [0..15]
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610]

你注意到((1 + sqrt 5)/ 2)ⁿ和(3 + sqrt 5)ⁿ的相似性.

从这里可以猜到,可能有一个类似于斐波那契的系列来计算这一点.

但是什么系列？所以你计算前几个项目:

ghci> let calcThing i = floor ((3 + sqrt 5) ^ i)
ghci> map calcThing [0..5]
[1,5,27,143,751,3935]

猜测公式是这样的:

事物_n = a*事物_n-1 + b*事物_n-2

我们有:

27 = a*5 + b*1

143 = a*27 + b*5

我们求解线性方程组得到:

东西_n = 4*东西_n-1 + 7*东西_n-2(a = 4,b = 7)

我们检查:

ghci> let thing = 1 : 5 : zipWith (+) (map (* 4) (tail thing)) (map (* 7) thing)
ghci> take 10 thing
[1,5,27,143,761,4045,21507,114343,607921,3232085]
ghci> map calcThing [0..9]
[1,5,27,143,751,3935,20607,107903,564991,2958335]

然后我们发现遗憾的是,这并没有计算我们的功能.但是,我们对它获得最正确的数字这一事实感到欢欣鼓舞.不理解为什么,但在这个事实的鼓舞下,我们尝试类似的东西.要查找已修改公式的参数:

事物_n = a*事物_n-1 + b*事物_n-2 + c

然后我们到达:

东西_n = 6*东西_n-1 - 4*东西_n-2 + 1

我们检查一下:

ghci> let thing =
        1 : 5 : map (+1) (zipWith (+)
          (map (*6) (tail thing))
          (map (* negate 4) thing))
ghci> take 16 thing == map calcThing [0..15]
True

Answer 2

我不知道如何解释，但问题的作者已经做了这个分析。