對酒當歌,人生幾何? 譬如朝露,去日苦多

2017年10月

1.入门视频:https://v.qq.com/x/page/i03233ew1gm.html

不过这个视频有个错误,就是定义结构体里的数组大小应该和单位矩阵数组大小一样。

2.入门题poj3070

代码:http://paste.ubuntu.com/25713501/

3.了解矩阵怎么相乘后就看十大经典题型吧!

(1)经典题目1 给定n个点,m个操作,构造O(m+n)的算法输出m个操作后各点的位置。操作有平移、缩放、翻转和旋转

解法:把所有操作化成一个矩阵,然后合并矩阵,再挨个乘点就可以了。

(2)经典题目2 给定矩阵A,请快速计算出A^n(n个A相乘)的结果,输出的每个数都mod p。

解法:直接矩阵快速幂就可以解决。

(3)经典题目3 给定矩阵A,求A + A^2 + A^3 + … + A^k的结果

解法:构建一个特殊的矩阵,然后K+1次矩阵快速幂减去单位矩阵。(矩阵的构建真是有意思)。

(4)经典题目4 顺次给出m个置换,反复使用这m个置换对初始序列进行操作,问k次置换后的序列

解法:类似第一题,先合并前m次矩阵,然后矩阵快速幂。

(5)经典题目5 《算法艺术与信息学竞赛》207页(2.1代数方法和模型,[例题5]细菌,版次不同可能页码有偏差)

解法:类似第一题,先构造出几个矩阵合并,然后矩阵快速幂。

(6)经典题目6 给定n和p,求第n个Fibonacci数mod p的值,n不超过2^31

解法:构造矩阵,矩阵快速幂。

(7)经典题目7 求出任何一个线性递推式的第n项

解法:不太懂。

(8)经典题目8 给定一个有向图,问从A点恰好走k步(允许重复经过边)到达B点的方案数mod p的值

解法:构造出矩阵,然后快速幂

(9)经典题目9 用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案,M<=5,N<2^31,输出答案mod p的结果

解法:由一个状态推出下一个状态,然后构造矩阵,快速幂。

(10)经典题目10 AC自动机+矩阵快速幂

解法:不太懂。(看样子类似9,构造巨难)。

4.总结一下上面的十大经典题型

一眼题:2

稍微构造一下矩阵:1,4,5,8

构造难:3,6,7,9,10

构造矩阵有:二维平面点的转移,根据图构造,矩阵里面还有矩阵的构建,序列位置的改变,Fibonacci数列构建,线性方程组,状态转移构建。(也就是线,图,线性方程组,矩阵里的矩阵,状态转移(多米诺骨牌))

5.kuangbin矩阵专题:https://vjudge.net/contest/71746

基本上是十大题型的扩展,大部分题型是菲波那切数列的变形和状态转移,由于各种原因,并没有做完,不过他们题型基本差不多的一个特点就是n和m一个特别大,一个特别小,矩阵水题ok了。

1.特别详细的一篇教程http://blog.csdn.net/zr459927180/article/details/51627910

但是看完第六部之后就不建议看第七部了。

2.因为我觉得下载EasyUEFI才是正解

3.如果你得电脑是acer,你必需看这一步,否则就不用看了。

http://tieba.baidu.com/p/4760148073?qq-pf-to=pcqq.group

4.修改双系统启动顺序和启动时间。

http://www.jianshu.com/p/f3c3beb7f205

5.时间错误调整。

https://jingyan.baidu.com/album/154b46317b25ca28ca8f41e8.html?qq-pf-to=pcqq.group