louhc

分类

未归档(78) 题解(81)

/ 注册

全部文章（共4篇）

题解|信息学奥赛一本通-提高篇 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