斐波那契数列问题的递归和动态规划2_

牛客_陈冠希

首先，递推公式为 f(n)=f(n-1)+f(n-2)
下面我们思考一个问题：[ f(n) f(n-1) ]^T 等于什么？

根据前面的递推公式，我能想到[ f(n-1)+f(n-2) f(n-2) ]^T

^{只是把矩阵的第一项带入了递推公式。}

^{那么我们得到如下的样子：}

[ f(n) f(n-1) ]^T=[ f(n-1)+f(n-2) f(n-2) ]^T

观察发现，前面是f(n)和f(n-1)，后面是包含f(n-1)和f(n-2)的式子，有没有什么办法，让后面的式子能提出来单独的一列是f(n-1)和f(n-2)呢？

^{也就是求一个A 满足}[ f(n-1)+f(n-2) f(n-2) ]^{T=A * [ f(n-1) f(n-2) ]^T}

^{A可能是数可能是个式子。}

^{根据矩阵乘法得出A确实存在且A=[ [1 1] [1 0] ]（注意这里没有转置啊）}

^{也就是说这道题根据上面的公式，变成了求[ [1 1] [1 0] ]的n-2次方得到的矩阵在乘以[f(2) f(1)]之后，上面的那个值就是f(n)。}

^{也就是说，这道题变成了求[ [1 1] [1 0] ]的n-2次方，找最快的方法算它。如果你在这用for循环的思路来乘，那你的思路还不如用for循环去遍历n，毕竟这矩阵乘法，遍历一遍加矩阵乘法，肯定不如单独遍历一遍。}

^{放着矩阵乘法运算不说。}

^{先说a的n次方你怎么算最快？}

^{先比方n等于5的话。}

^{我会把a的5次方拆成 a的4次方 * a的1次方}

^{n等于7的话。}

^{我会拆成 a的4次方 * a的平方 * a的1次方}

^{其实就相当于拆分指数为2的次幂的和}

^{公式为 n = x}_i * 2^a xi只能是1或者0

用这种思路，每次只需要n=n/2即可。如果n是奇数的话，还需要额外相乘一次。

于是，整体思路全部都有了，有几个疑问，大家需要自己思考一下。

本文第二行是如何思考得来的，就是说，我应该怎么想就能想到将这个问题转换为矩阵。
矩阵的n次方如何快速运算。
最后如何通过矩阵乘法还原到 f(n)的结果是多少

发表于 2019-08-26 18:08:45 回复(0)

Java

pein531

这个数据范围，有点过分…有点过分啊。常规动态规划的O(N)算法完全不行，必须使用矩阵快速幂的算法，设斐波那契数列的第i项为f_i，对于某一项依赖前两项的二阶问题，都可以写成如下的通式：

$[f_{n},f_{n-1}]=[f_{n-1},f_{n - 2}]*\left[ \begin{matrix} a& b \\ c & d \\ \end{matrix} \right]$

对于斐波那契数列问题，可以根据前几项的初始值，可以解方程得到a=b=c=1，d=0。将等式右边的斐波那契矩阵递归替换直到初始值，可以得到

$[f_{n},f_{n-1}]=[f_{2},f_{1}]*\left[ \begin{matrix} 1& 1 \\ 1 & 0 \\ \end{matrix} \right]^{n-2}$

于是只要后面矩阵的次幂计算能够加速，就可以降低O(N)这个时间复杂度。这里可以利用矩阵的快速幂算法。首先考虑某个标量的快速幂：如10⁷⁵，75的二进制表示为(1001011)₂，记最终的结果为res=1，底数base=10，从最低位开始，最低位为1，将base乘进res，然后base平方；看倒数第二位为1，又将base乘进res，base继续平方；看倒数第三位为0（75不断右移并与1进行与运算可以知道最后一位是不是1），base不乘进res，但是它会继续平方……，周而复始直到遍历完75的最高位，算出的结果res就是我们要的答案。矩阵乘法同理，我们将标量的1对应为n阶单位矩阵，乘法用矩阵乘法就好。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    final static int MOD = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        long[][] base = {{1, 1}, {1, 0}};
        long[][] res = {{1, 0}, {0, 1}};     // 单位矩阵
        if(n <= 3){
            System.out.println(n);     // 小于等于3直接输出
        }else{
            long p = n - 1;
            for(; p != 0; p >>= 1){
                if((p & 1) != 0) res = multiMat2D(res, base);
                base = multiMat2D(base, base);
            }
            System.out.println((res[0][0] + res[1][0]) % MOD);
        }
    }
    
    private static long[][] multiMat2D(long[][] A, long[][] B) {
        return new long[][]{{(A[0][0] * B[0][0] % MOD) + (A[0][1] * B[1][0] % MOD), (A[0][0] * B[0][1] % MOD) + (A[0][1] * B[1][1] % MOD)}, 
                            {(A[1][0] * B[0][0] % MOD) + (A[1][1] * B[1][0] % MOD), (A[1][0] * B[0][1] % MOD) + (A[1][1] * B[1][1] % MOD)}};
    }
}

发表于 2021-11-25 10:36:11 回复(0)

C/C++

尹恒20190801200404

非矩阵的解法，更快代码更少：

#include<bits/stdc++.h>
#define ll long long
#define p 1000000007
using namespace std;

ll n;
map<ll,ll> mp;

ll calc(ll n){
    if(mp[n])return mp[n];
    ll tmp = n;
    n/=2;
    if (tmp%2) return mp[tmp]=calc(n)*calc(n)%p+calc(n+1)*calc(n+1)%p;
	else return mp[tmp]=(2*calc(n-1)%p+calc(n)%p)*calc(n)%p;
}

int main(){
    scanf("%lld", &n);
    mp[1] = 1;
    mp[2] = 1;
    cout<<calc(n+1)%p;
    return 0;
}

发表于 2020-02-12 21:51:10 回复(0)

C/C++

宫经磊

#include <bits/stdc++.h>
using namespace std;
const long long MOD=1e9+7;
long long n;
void mat_mul(long long a[2][2],long long b[2][2]){
	long long tmp[2][2];
	int i,j,k;
	memset(tmp,0,sizeof(tmp));
	for(i=0;i<2;i++){
		for(j=0;j<2;j++){
			for(k=0;k<2;k++){
				tmp[i][j]+=b[i][k]*a[k][j]%MOD;
				tmp[i][j]=tmp[i][j]%MOD;
			}
		}
	}
	memcpy(a,tmp,sizeof(tmp));
}
long long slove(long long n){
	long long ret[2][2]={{0,1},{1,1}};
	long long dp[2][2]={{1,0},{2,0}};
	while(n){
		if(n&1) mat_mul(dp,ret);
		mat_mul(ret,ret);
		n>>=1;
	}
	return dp[1][0];
}
int main(){
	scanf("%lld",&n);
	printf("%lld",slove(n-2));
	return 0;
}

发表于 2023-01-18 13:03:21 回复(0)

静静流淌

import java.util.*;
public class Main{
    static long modv = 1000000007;
    static long [][] mulMatrix(long [][] a, long [][] b){
        int row = a.length;
        int col = b[0].length;    /*(a,b)*(b,c) = (a,c)*/
        int num = a[0].length;
        long [][] res = new long[row][col];
        for(int i = 0;i < row;++i)
            for(int j = 0;j < col;++j){
                res[i][j] = 0;                // 这个可以不用java默认是0
                for(int k = 0;k < num;++k)    // a的行 * b的列
                    res[i][j] = (res[i][j]+( (a[i][k] % modv) * (b[k][j] % modv) ) % (modv))%modv;         
            }
        return  res;
    }
    
    static long [][] matrixPower(long [][] m,long p){
        int num = m.length;
        long [][] res = new long[num][num];
        for(int i = 0;i < num;++i)   /*单位矩阵*/
            res[i][i] = 1;
        long [][] tmp = m;
        // 注意这里 p >>= 1 不能用 p /= 2替代
        for(;p > 0;p >>= 1){
            // 如果是奇数，开始和结束会调用一次，偶数只有最后调用一次
            if((p&1) == 1){
                res = mulMatrix(res,tmp);
            }
            tmp = mulMatrix(tmp,tmp);
        }
        return res;
    }
    
    
    public static void main(String [] args){
        Scanner input = new Scanner(System.in);
        long n = input.nextLong();
        if(n == 2 || n == 1){
            System.out.printf("%l\n",n);
            return;
        }
        long [][] t_m = {{1,1},{1,0}};
        long [][] start = {{2},{1}};  
        long [][] tmp = matrixPower(t_m,n-2);
        tmp = mulMatrix(tmp,start);
//         System.out.println(tmp[0][0]);
        // Java中没有%ld 和 %d这种写法
        System.out.printf("%d\n",tmp[0][0]);
    }
}

发表于 2021-03-29 19:03:17 回复(0)

Java

jahentao

求出二阶递推数列 $二阶递推数列$ 的状态矩阵 $状态矩阵$ 。

$图片说明$

用矩阵快速幂求解矩阵幂。

注意到N的范围 $图片说明$ ，用8个字节整数表示。

import java.util.*;

public class Main {

    public static final int mod = 1_000_000_007;

    public static long[][] multiply(long[][] matrix1, long[][] matrix2) {
        long[][] res = new long[matrix1.length][matrix1.length];

        for (int i = 0; i < matrix1.length; i++) {
            for (int j = 0; j < matrix1.length; j++) {
                long sum = 0;
                for (int k = 0; k < matrix1.length; k++)
                    sum = (sum + (matrix1[i][k] * matrix2[k][j]) % mod) % mod;
                res[i][j] = sum;
            }
        }
        return res;
    }

    public static long[][] powerN(long N, long[][] matrix) {
        long[][] res = new long[matrix.length][matrix.length];
        for (int i = 0; i < res.length; i++) 
            res[i][i] = 1;
        while (N != 0) {
            if ((N & 1) == 1) {
                res = multiply(res, matrix);
            }
            matrix = multiply(matrix, matrix);
            N = N >>> 1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        sc.close();
        if (N < 1) {
            System.out.println(0);
            return;
        }
        if (N == 1) {
            System.out.println(1);
            return;
        }
        long[][] matrix = {{1, 1}, {1, 0}};
        long[][] res = powerN(N - 1, matrix);
        System.out.println((2 * res[0][1] + res[1][1]) % mod);
    }
}

发表于 2020-05-18 16:56:25 回复(0)

HPrevInstance

快速模幂+矩阵优化，网上非常多hh，附上GoLang代码

package main
 
 
import "fmt"
 
type SQ struct {
    m,n int
    data [][]int
}
func mul(a SQ,b SQ) [][]int{
    res := [][]int{}
    for i :=0;i<a.n;i++ {
        t := []int{}
        for j :=0;j<b.m;j++ {
            r := 0
            for k:=0;k<a.m;k++ {
                r += a.data[i][k]*b.data[k][j]
                r=r%1000000007
            }
            t = append(t, r)
        }
        res = append(res,t)
    }
    return res
}
 
func fibonacci(n int) int {
    sum:=SQ{
        m:2,
        n:2,
        data:[][]int{
            {1,0},
            {0,1},
        },
    }
    a:=SQ{
        m:2,
        n:2,
        data:[][]int{
            {1,1},
            {1,0},
        },
    }
    for n>0{
        if n&1==1{
            sum.data=mul(a,sum)
        }
        a.data=mul(a,a)
        n>>=1
    }
    return sum.data[0][0]
}
 
func main(){
    var n int
    fmt.Scan(&n)
    fmt.Println(fibonacci(n))
}

发表于 2019-12-28 13:23:08 回复(0)

Emars

import java.util.Scanner;

public class Main {
    /**
     * 矩阵乘法
     * @param A
     * @param B
     * @return
     */
    static long MAX = (long) (1e9 + 7);
    static long[][] dot(long[][] A, long[][] B) {
        assert (A[0].length == B.length);
        long tmp;
        long[][] R = new long[A.length][B[0].length];
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B[0].length; j++) {
                for (int k = 0; k < A[0].length; k++) {
                    R[i][j]+= A[i][k]* B[k][j];
                }
                R[i][j] = (long) (R[i][j]%MAX);
            }

        }
        return R;
    }

    /**
     * 矩阵快速幂模
     * @param a
     * @param b
     * @return
     */
    public static long[][] quickMod(long[][] a, long b) {
        long[][] ans = new long[2][2];
        b=b-2;
        //初始化为单位矩阵
        for(int i=0;i<2 ;++i) {
            ans[i][i] = 1;
        }
        //计算矩阵乘法
        while (b != 0) {
            if ((1 & b) == 1) {
                ans = dot(ans, a);
            }
            b >>= 1;
            a = dot(a , a) ;
        }
        return ans;
    }


    /**
     * 斐波那契通用公式：
     * {F(n),F(n-1)} = {{1, 0，1}, {1,0， 0}，{0，1，0}}^(n-3) *  {F(3),F(2)，F(1)}
     * @param args
     */
    public static void main(String[] args) {
        long[][] A = new long[][]{{1, 1}, {1, 0}};
        long[][] B = new long[2][2];
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        if (n > 2) {
            B= quickMod(A,n);
            long rs = (long) (2*B[0][0]+B[0][1])%MAX;
            System.out.println(rs);
        } else {
            System.out.println(n);
        }

    }
}

发表于 2019-10-08 17:07:37 回复(0)

天命剑主

#include <cstring>

using std::memcpy;
using std::memset;

#include <iostream>

using std::ostream;
using std::endl;

template<typename T>
/**
 * 矩阵类
 * @tparam T 类型参数
 */
class matrix {
public:
    int row;//行
    int column;//列
    T **data;//数据

public:
    matrix(int r, int c) : row(r), column(c) {
        data = new T *[r];
        for (int i = 0; i < r; ++i) {
            data[i] = new T[c];
            memset(data[i], 0, column * sizeof(*data[i]));
        }
    }

    matrix(const matrix &m) : row(m.row), column(m.column) {
        data = new T *[row];
        for (int i = 0; i < row; ++i) {
            data[i] = new T[column];
            memcpy(data[i], m.data[i], column * sizeof(*data[i]));
        }
    }

    matrix(int r, int c, T **m) : row(r), column(c) {
        data = new T *[row];
        for (int i = 0; i < row; ++i) {
            data[i] = new T[column];
            memcpy(data[i], m[i], column * sizeof(*data[i]));
        }
    }

    matrix &operator=(const matrix &m) {
        if (&m == this) {
            return *this;
        }
        for (int i = 0; i < row; ++i) {
            delete[] data[i];
        }
        delete[] data;
        row = m.row;
        column = m.column;
        data = new T *[row];
        for (int i = 0; i < row; ++i) {
            data[i] = new T[column];
            memcpy(data[i], m.data[i], column * sizeof(*data[i]));
        }
        return *this;
    }

    bool operator==(const matrix &m) const {
        if (row != m.row || column != m.column) {
            return false;
        }
        for (int r = 0; r < row; ++r) {
            for (int c = 0; c < column; ++c) {
                if (m[r][c] != data[r][c]) {
                    return false;
                }
            }
        }
        return true;
    }

    inline bool operator!=(const matrix &m) const {
        return !operator==(m);
    }

    inline matrix operator*(const matrix &m) {
        return multiply(m);
    }

    inline matrix &operator*=(const matrix &m) {
        *this = multiply(m);
        return *this;
    }

    /**
     * 矩阵乘法
     * @param m 被乘数
     * @return 结果
     */
    matrix multiply(const matrix &m) {
        matrix<T> c(row, m.column);
        for (int i = 0; i < row; ++i) {
            for (int k = 0; k < m.row; ++k) {
                for (int j = 0; j < m.column; ++j) {
                    c[i][j] = (c[i][j] + data[i][k] * m[k][j]);
                }
            }
        }
        return c;
    }

    /**
     * 矩阵乘法
     * @param m 被乘数
     * @param mod 结果太大的时候求mod
     * @return 结果
     */
    matrix multiply(const matrix &m, T mod) {
        matrix<T> c(row, m.column);
        for (int i = 0; i < row; ++i) {
            for (int k = 0; k < m.row; ++k) {
                for (int j = 0; j < m.column; ++j) {
                    c[i][j] = (c[i][j] + data[i][k] * m[k][j]) % mod;
                }
            }
        }
        return c;
    }

    /**
     * 求矩阵m的n次幂
     * 注意m.row == m.column
     * @param n n次幂
     * @return 结果
     */
    matrix pow(unsigned long long n) {
        matrix<T> m = *this;
        matrix<T> res(m.row, m.row);
        for (int i = 0; i < m.row; ++i) {
            res[i][i] = 1;
        }
        while (n > 0) {
            if (n & (unsigned)1) {
                res = res.multiply(m);
            }
            m = m.multiply(m);
            n >>= 1;
        }
        return res;
    }

    /**
     * 求矩阵m的n次幂
     * 注意m.row == m.column
     * @param n n次幂
     * @param mod 结果太大的时候求mod
     * @return 结果
     */
    matrix pow(unsigned long long n, T mod) {
        matrix<T> m = *this;
        matrix<T> res(m.row, m.row);
        for (int i = 0; i < m.row; ++i) {
            res[i][i] = 1;
        }
        while (n > 0) {
            if (n & (unsigned)1) {
                res = res.multiply(m, mod);
            }
            m = m.multiply(m, mod);
            n >>= 1;
        }
        return res;
    }

    ~matrix() {
        for (int i = 0; i < row; ++i) {
            delete[] data[i];
        }
        delete[] data;
    }

    T *&operator[](int r) const {
        return data[r];
    }

    friend ostream &operator<<(ostream &os, const matrix &m) {
        os << "matrix : ";
        for (int i = 0; i < m.row; ++i) {
            if (i != 0) {
                os << "         ";
            }
            for (int j = 0; j < m.column; ++j) {
                os << m[i][j] << " ";
            }
            os << endl;
        }
        return os;
    }
};

template<typename T>
T fast_fibonacci(unsigned long long n, T mod) {
    matrix<T> m(2, 2);
    m[0][0] = 1;
    m[0][1] = 1;
    m[1][0] = 1;
    m[1][1] = 0;
    m = m.pow(n, mod);
    return m[1][0];
}

#include <iostream>
using std::cout;
using std::cin;

unsigned long long m = 1e9 + 7;

int main(){
    unsigned long long n = 0;
    cin >> n;
    cout << fast_fibonacci(n+1,m) << endl;
}

发表于 2019-08-29 10:03:18 回复(0)

斐波那契数列问题的递归和动态规划2

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题