louhc

题解

未归档(78)

/ 注册

全部文章 / 题解（共7篇）

题解 | 信息学奥赛一本通 GT考试

思路先不考虑数据范围,我们设表示当前构造到第位,已经匹配了位的方案数.最终答案即为我们可以写出一个递推式,是我们要求的系数.我们可以使用KMP来求系数.只要求出前位(长度为)与相同,下一位的数字为时,与最大的匹配长度.对于每一个,,很明显不能承受.但是系数每次转移都不会变,因此直接用矩阵快速幂优化...

字符串矩阵乘法快速幂 KMP

2019-08-24

0 552

题解 | 信息学奥赛一本通迷路

思路首先,假设图中所有路径长度都为1.走步时从到的方案数,走步时从到的方案数.那么走步的方案数.矩阵快速幂就OK了.但是这里边权不为1.由于数据范围小,我们可以将边权为的边拆成条边权为1的边,然后矩阵快速幂即可.复杂度为代码 #include<bits/stdc++.h> using...

二进制拆分矩阵乘法快速幂

2019-08-24

0 594

题解|信息学奥赛一本通-提高篇 Fibonacci

思路矩阵加速递推基础题.因为,可以构造出矩阵. 然后跑矩阵快速幂即可.代码中的矩阵可能稍微有点不同,毕竟是以前写的代码.不过只要理解矩阵加速递推就没问题了.由于这是多组数据,一种优化方法是将全部存起来(其中表示递推矩阵).大概可以减少一半的常数.注意边界问题复杂度大概为代码 #include&l...

矩阵乘法斐波那契数列快速幂

2019-08-20

0 717

题解|信息学奥赛一本通-提高篇佳佳的Fibonacci

思路这题有好几种做法.你可以构造的矩阵,也可以的,还可以的.这里就讲的吧... 然后只要算出和就OK了.时间复杂度代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i...

矩阵乘法快速幂斐波那契数列

2019-08-20

3 714

题解|信息学奥赛一本通-提高篇 Fibonacci前n项和

思路这题有两种思路. 思路1 构造矩阵直接求出然后跑矩阵快速幂即可. 思路2 怎么证明呢?我们可以使用数学归纳法. 时显然成立.对于,.因此就相当于求斐波那契数列第n+2项-1.很明显思路2的时间/空间/代码复杂度都更加优秀. 代码 #include<bits/stdc++.h> us...

矩阵乘法快速幂斐波那契数列

2019-08-20

2 848

题解|信息学奥赛一本通-提高篇 Fibonacci第n项

思路矩阵加速递推基础题.因为,可以构造出矩阵. 然后跑矩阵快速幂即可.矩阵构造方法很多,怎么构造开心就好.注意一些小细节,因为可能是,最后输出是也最好取模一下.平时写矩阵就注意下常数优化.毕竟矩阵乘法的常数还是比较大的. 代码 #include<bits/stdc++.h> using...

斐波那契数列矩阵乘法快速幂

2019-08-20

0 611

题解 | 信息学奥赛一本通-提高篇矩阵 A×B

思路很基本的矩阵乘法.直接根据矩阵乘法的定义暴力求解即可.别忘了开long long. 复杂度为.事实上还有一种更优秀的做法Strassen可以把复杂度优化到.不过话说回来一般不会遇到这么毒瘤的出题人来卡你,感兴趣的童鞋可以去网上查找资料. 代码 #include<bits/stdc++.h...

矩阵乘法

2019-08-20

0 611