Nowcoder 105G 又见斐波那契 (矩阵快速幂)
类斐波那契数的题目,给定递推式 f(0) = 0, f(1) = 1, f(i) = f(i-1) + f(i-2) + i^3 + i^2 + i + 1 ,求解该数列的第 n 项。
继续踏上旅途,在没有你的春天……
类斐波那契数的题目,给定递推式 f(0) = 0, f(1) = 1, f(i) = f(i-1) + f(i-2) + i^3 + i^2 + i + 1 ,求解该数列的第 n 项。
Fibonacci 数是非常有名的一个数列,它的公式为 f(n)=f(n-1)+f(n-2), f(0)=1, f(1)=2 。
我们可以把任意一个数 x 表示成若干不相同的 Fibonacci 数的和,比如说 14 = 13+1 = 8+5+1 = 8+3+2+1。
如果把 Fibonacci 数列作为数的位权,即 f(i) 作为第 i 位的位权,每位的系数只能是 0 或者 1 ,从而得到一个 01 串。 比如 14 可以表示成 100001, 11001, 10111 。我们再把这个 01 串看成 2 进制,再转成 10 进制以后就变成了 33, 25, 23 。为了避免歧义,我们将使用最小的那个值 23 。
每一个正整数都可以表示为若干个斐波那契数的和,一个整数可能存在多种不同的表示方法,例如:14 = 13 + 1 = 8 + 5 + 1,其中13 + 1是最短的表示(只用了2个斐波那契数)。定义F(n) = n的最短表示中的数字个数,F(14) = 2,F(100) = 3(100 = 3 + 8 + 89),F(16) = 2(16 = 8 + 8 = 13 + 3)。定义G(n) = F(1) + F(2) + F(3) + …… F(n),G(6) = 1 + 1 + 1 + 2 + 1 + 2 = 8。给出若干个数字n,求对应的G(n)。
给出 f(n) 的递推式以及 n 的值,求 f(n)%2 的结果。
给出 n,m,p 三个整数,求斐波那契数列前 n 项和与前 m 项和的最大公约数模 p 。
求斐波那契数列的第多少项,因为数据范围比较大,所以采用矩阵快速幂的方法求得。