如何解决:f(n)= f(n - 1)+ 3 * f(n - 2)+ 3 * f(n)+ f(4)

How can I solve

我怎样才能解决

f(n) = f(n-1) + 3*f(n-2) + 3*f(n-3) + f(n-4) maximum value of n = 10^18 minimum is 1
initial conditions are
f(1) = 1
f(2) = 3
f(3) = 3
f(4) = 1

when f(n) can be large? print f(n) modulus 10000007

当f(n)可以很大时?打印f(n)模量10000007

My try to this problem was as follows (may be wrong in using the modulo)

我对这个问题的尝试是这样的(使用模块化可能是错误的)

1st test case:
3
2
5
9

output:
3
20
695
(working fine)

2nd tst case:
3
1554894
5959595
2562651

output:
7505501
9551828
6592801
(working fine)

but for larger number the program fails; why?

但是对于较大的数字，程序失败;为什么?

#!/usr/bin/python
T = int(raw_input())
def fib_iter(n):
    if n == 1:
        return 1
    if n == 2:
        return 3
    if n == 3:
        return 3
    if n == 4:
        return 1   
    prev1, prev2, prev3, prev4 = 1, 3, 3, 1

    i = 5
    while i < n+1:
        curr = (prev1%10000007 + 3*prev2%10000007 + 3*prev3%10000007 + prev4%10000007)%10000007
        prev1, prev2, prev3, prev4 = prev2%10000007, prev3%10000007, prev4%10000007, curr%10000007
        i = i + 1
    return curr%10000007

for t in xrange(T):
    n = int(raw_input())
    print fib_iter(n)

4 个解决方案

#1

Read this book, then solve it by hand.

读这本书，然后用手解决。

EDIT: as I was asked to provide more details: With "solving", I meant to derive an explicit formula which directly gives you the coefficient f(n) [such that there is no recursion necessary]. For the normal Fibonacci series, such is given by the Binet formula. Following the recipe in the linked book, you can do it with the following steps:

编辑:当我被要求提供更多的细节:“解决”时，我的意思是推导出一个明确的公式，直接给出系数f(n)[这样就不需要递归了]。对于一般的斐波那契数列，由Binet公式给出。按照链接书中的食谱，你可以按照以下步骤来做:

Derive the generating function of the n-th coefficient. Basically, this is done by considering a function which has a power series expansion in terms of the sought coefficients f(n), and combining the several terms into one function.

推导出n次系数的生成函数。基本上，这是通过考虑一个函数，它有一个幂级数展开式的系数f(n)，并将几个项合并成一个函数。
Given the generating function, derive the expansion coefficient standing in front of the monomial x^n. As the generating function you specified contains at most fourth order polynomials, this can even be done analytically.

考虑到生成函数,推导出膨胀系数站在前面的单项x ^ n。由于您指定的生成函数包含最多四阶多项式，这甚至可以进行解析。

If there were some math mode here I would provide more mathematical details, and with some luck also the solution. But just try it like this, it is easy and the book is well readable.

如果这里有一些数学模式的话，我会提供更多的数学细节，也会带来一些运气。但就像这样试试，很容易，而且这本书读起来很好。

#2

update - try changing those two lines in the loop to:

更新—尝试将循环中的这两行更改为:

    curr = (prev1 + 3*prev2 + 3*prev3 + prev4)%10000007
    prev1, prev2, prev3, prev4 = curr, prev1, prev2, prev3

With modulus 10000007, n = 15616511848, you should get 5370032 as you mentioned. Note that 10000007 = 941 x 10627 and is not prime. I'm not sure why it was chosen. Typically these type of problems use 1000000007 (7 + 10^9) which is a prime number.

使用模量10000007,n = 15616511848，你应该得到5370032。注意10000007 = 941 x 10627并不是质数。我不知道为什么选它。通常,这些类型的问题使用1000000007(7 + 10 ^ 9)这是一个质数。

Speeding up this algorithm is more of a math problem than a programming problem. The matrix form for this is:

加速这个算法比编程问题更像是一个数学问题。这个矩阵的形式是:

       |  1  3  3  1 |
   a = |  1  0  0  0 |
       |  0  1  0  0 |
       |  0  0  1  0 |

       |  1 |
x[4] = |  3 |
       |  3 |
       |  1 |

x[i+1] = a x[i]

x[i+j] = a^j x[i]

Repeated squaring can be used to speed up calculating a^j .

重复平方可用于加快计算^ j。

In case you're curious x[0] through x[4] without the modulus. For the modulus, add the modulus (10000007) to the negative numbers:

如果你好奇x[0]到x[4]没有模量。对于模量，将模量(10000007)加入负数:

x[0] =  -14,  39, -73, 117
x[1] =    1, -14,  39, -73
x[2] =    3,   1, -14,  39
x[3] =    3,   3,   1, -14
x[4] =    1,   3,   3,   1

#3

Using the matrix method the execution becomes very fast and reliable. http://x-perienceo.blogspot.in/

使用矩阵方法，执行变得非常快速和可靠。http://x-perienceo.blogspot.in/

#4

I wrote a more elaborate answer here.

我在这里写了一个更详细的答案。

It is important to know that 1000007 is prime. Therefore you can use Euler's Theorem. Euler's Theorem states that for a prime number p, a**x % p == a**y % p (Python notation) if x % (p-1) == y % (p-1).

知道1000007是质数是很重要的。因此你可以用欧拉定理。欧拉定理指出，对于质数p，如果x % (p-1) == y % (p-1)，那么a**x % p == a**y % p (Python表示法)。
Try to find a matrix notation to compute f(n) for any n without first recursively having to compute f(n-1) and so on. Then use exponentiation by squaring to compute it (up to your modulo as stated in 1. above).

试着找一个矩阵表示法来计算f(n)对于任何n，不需要先递归地计算f(n-1)等等。然后用求幂的平方来计算它(直到你的模态，如1所示)。如上图所示)。

#1