矩阵快速幂小结

      矩阵快速幂大概是用来解决这样一类问题,当你知道了一个递推式比如a[n]=a[n-1]+a[n-2] 题目要求你求出a[n]。如果n大于1亿怎么办?

不可能用for。解决办法就是根据递推式构造一个矩阵A,最终会化简为a[n]=A^n类似的形式,再利用快速幂,快速的求出A^n,所以原先的

O(n)就变成了O(logn) 

例如POJ 3233 递推关系是 s[k]=s[k-1]+A^k; 

所以s[K]=( | 1  0| ^n )*s[1]

                | 1  A|

     下面给出矩阵快速幂的模板

      矩阵连乘:

struct Node
{
    int a[25][25];
};
int n,m,x,y,k,t;
Node multiply(Node a,Node b)
{
    Node c;
    memset(c.a,0,sizeof(c.a));
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(!a.a[i][j]) continue;

//减枝,有些题目写减枝才可以过,n有些大的时候。有的题目n有500,n^3就会炸了,这类题目,要观察矩阵的形式,可以把矩阵转
换的,用n^2就可以完成连乘,例如POJ 3150 后面的例题里有
            for(int k=0;k<n;k++)
            {
                (c.a[i][k]+=(a.a[i][j]*b.a[j][k])%mod)%=mod;
            }
        }
    }
    return c;
}

矩阵快速幂:

Node quick(Node a,int x)
{
    Node c;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        c.a[i][j]=(i==j?1:0);
    for(x;x>0;x>>=1)
    {
        if(x&1) 
	   c=multiply(c,a);
        a=multiply(a,a);
     }
    return c;
}

练习题目:

http://poj.org/problem?id=3233

题解:

http://blog.csdn.net/dacc123/article/details/51204052

http://poj.org/problem?id=3735

题解:

http://blog.csdn.net/Dacc123/article/details/51204080

http://poj.org/problem?id=3150

题解:

http://blog.csdn.net/dacc123/article/details/51222518

http://acm.hdu.edu.cn/showproblem.php?pid=2604

题解:

http://blog.csdn.net/dacc123/article/details/51207863

http://acm.hdu.edu.cn/showproblem.php?pid=2157

题解:

http://blog.csdn.net/dacc123/article/details/51205684

http://acm.hdu.edu.cn/showproblem.php?pid=1575

题解:

http://blog.csdn.net/dacc123/article/details/51205878

http://poj.org/problem?id=3070

题解:

http://blog.csdn.net/dacc123/article/details/51222489

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏祝威廉

从DataFrame自动化特征抽取的尝试

虽然提供了很多Estimator/Transformer, 正如这篇文章所显示的,如何基于SDL+TensorFlow/SK-Learn开发NLP程序,处理的代...

9230
来自专栏WindCoder

最大流量和线性分配问题

这里有一个问题:你的业务分配给承包商来履行合同。您可以浏览您的名单,并决定哪些承包商可以参与一个月的合同,你可以查看你的合同,看看哪些合同是一个月的任务。鉴于你...

28320
来自专栏冰霜之地

Google S2 是如何解决空间覆盖最优解问题的?

这篇不出意外就是 Google S2 整个系列的最终篇了。这篇里面会把 regionCoverer 算法都讲解清楚。至于 Google S2 库里面还有很多其他...

41530
来自专栏章鱼的慢慢技术路

《算法图解》第一章笔记与课后练习

39640
来自专栏ACM算法日常

不同路径(动态规划)- leetcode 62

最近在看leetcode的题目,都是面试题,需要面试的同学可以努力刷这里的题目,因为很多公司的面试笔试题都是参考这个上面的。相对OJ上的题目,感...

18840
来自专栏机器学习算法与Python学习

机器学习(31)之频繁集挖掘FP Tree详解

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第一 【Python】:排名第三 【算法】:排名第四 明早7:22推送第2期免费送书活动 ...

43660
来自专栏小詹同学

Leetcode打卡 | No.011 盛最多水的容器

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

18520
来自专栏swag code

编程:判断一个数是否是奇数?(93.7%的人会写错)

看似是对的,但是每执行四次(四分之一错误)便会有一个错误的结果(用数据说话)。考虑到负奇数的情况,它除以2的结果就不会是1。因此,返回值是false,而这样是不...

9640
来自专栏owent

PKU POJ 1724 ROADS 解题报告

题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=1724

7220
来自专栏Java成神之路

文本相似度——自己实现文本相似度算法(余弦定理)

最近由于工作项目,需要判断两个txt文本是否相似,于是开始在网上找资料研究,因为在程序中会把文本转换成String再做比较,所以最开始找到了这篇关于 距离编辑算...

25630

扫码关注云+社区

领取腾讯云代金券