矩阵快速幂:PIPI的数学题IV

梦想不抛弃苦心追求的人,只要不停止追求,你们会沐浴在梦想的光辉之中。再美好的梦想与目标,再完美的计划和方案,如果不能尽快在行动中落实,最终只能是纸上谈兵,空想一番。只要瞄准了大方向,坚持不懈地做下去,才能够扫除挡在梦想前面的障碍,实现美好的人生蓝图。矩阵快速幂:PIPI的数学题IV,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

矩阵快速幂:PIPI的数学题IV

问题:

在这里插入图片描述
在这里插入图片描述

思路:

  求斐波拉契数列实际上是一个DP问题,DP的状态转移方程已经给出了,问题在于用给出的状态转移方程进行线性递推,时间复杂度是O(n)的。然而本题的n达到了1e10的规模,肯定会超时,那么有什么办法能优化呢?答案是矩阵快速幂。
  快速幂是什么这里就不多说了,给个传送门:数学专题:同余定理、gcd与lcm、中位数定理、筛法、快速幂等
  那么什么是矩阵快速幂?矩阵快速幂其实就是将DP的状态转移方程通过矩阵相乘的形式表示,再通过快速幂的方法,降低时间复杂度。比如使用矩阵快速幂,该题O(n)的时间复杂度将降至O(logn)
  我们先来看DP[2] = DP[1] + DP[0],我们可以构造这样一个矩阵相乘来求出DP[2]:
在这里插入图片描述
  那么如何求出DP[3],再乘以一个我们所构造的矩阵即可:
在这里插入图片描述
  依次类推,我们可以发现规律如下:
在这里插入图片描述
  于是,对于求DP[n],我们就可以不使用线性递推,而是通过矩阵幂的方法求出。根据快速幂算法,只需要做logn次矩阵乘法就可以计算出第二个矩阵的n-1次幂是多少。而这是个2*2的矩阵,每做一次矩阵乘法的复杂度为一个常数。因此使用矩阵快速幂就可以把时间复杂度从O(n)优化成O(logn)。

  一般矩阵快速幂都是和DP联系在一起的,当找到DP状态转移方程,但规模很大的话,可以考虑构造矩阵快速幂进行优化

代码:

import java.util.*;

public class Main {
    static long[][] startMatrix = new long[2][2];
    static long[][] mulMatrix = new long[2][2];
    static final long MOD_NUM = (long) (1e9 + 7);
    public static void main(String[] args) {
        startMatrix[0][0] = 1;
        startMatrix[0][1] = 1;
        mulMatrix[0][0] = 1;
        mulMatrix[0][1] = 1;
        mulMatrix[1][0] = 1;
        long k;
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLong()) {
            k = scanner.nextLong();
            System.out.println(fastMatrixPow(startMatrix, k - 1)[0][0] % MOD_NUM);
        }

    }

    static long[][] fastMatrixPow(long[][] matrix, long powNum) {
        long[][] baseMatrix = mulMatrix;
        while (powNum != 0) {
            if ((powNum & 1) == 1) {
                matrix = mulMatrix(matrix, baseMatrix);
            }
            baseMatrix = mulMatrix(baseMatrix, baseMatrix);
            powNum >>= 1;
        }
        return matrix;
    }

    static long[][] mulMatrix(long[][] matrix1, long[][] matrix2) {
        long[][] ans = new long[2][2];
        ans[0][0] = (matrix1[0][0] * matrix2[0][0] % MOD_NUM)
                    + (matrix1[0][1] * matrix2[1][0] % MOD_NUM);
        ans[0][1] = (matrix1[0][0] * matrix2[0][1] % MOD_NUM)
                + (matrix1[0][1] * matrix2[1][1] % MOD_NUM);
        ans[1][0] = (matrix1[1][0] * matrix2[0][0] % MOD_NUM)
                + (matrix1[1][1] * matrix2[1][0] % MOD_NUM);
        ans[1][1] = (matrix1[1][0] * matrix2[0][1] % MOD_NUM)
                + (matrix1[1][1] * matrix2[1][1] % MOD_NUM);
        return ans;
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/153709.html

(0)
飞熊的头像飞熊bm

相关推荐

发表回复

登录后才能评论
极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!