第一题 hdu 1757 A Simple Math Problem
思路：矩阵快速幂
分析:
1 最简单的矩阵快速幂的题目，直接利用矩阵求解即可
第二题 hdu 1575 Tr A
思路: 矩阵快速幂
分析:
1 题目给定一个n*n的矩阵要求矩阵的k次幂之后的矩阵的对角线的和
2 矩阵快速幂的裸题
第三题 hdu 2604 Queuing
思路: 递推+矩阵快速幂
分析;
1 根据题目的意思，我们可以求出F[0] = 0 , F[1] = 2 , F[2] = 4 , F[3] = 6 , F[4] = 9 , F[5] = 15
2 那么根据上面前5项我们可以求出n >= 5的时候 F[n] = F[n-1]+F[n-3]+F[n-4]
那么我们就可以构造出矩阵
| 1 0 1 1 | | F[n-1] | | F[n] |
| 1 0 0 0 | * | F[n-2] | = | F[n-1] |
| 0 1 0 0 | | F[n-3] | | F[n-2] |
| 0 0 1 0 | | F[n-4] | | F[n-3] |
第四题 hdu 2256 Problem of Precision
思路: 矩阵快速幂
分析:
1 题目要求的是(sqrt(2)+sqrt(3))^2n %1024向下取整的值
3 这里很多人会直接认为结果等于(an+bn*sqrt(6))%1024，但是这种结果是错的，因为这边涉及到了double，必然会有误差，所以根double有关的取模都是错误的思路
第五题 codeforces 185A Plant
思路: 递推+矩阵快速幂
分析:
1 题目要求找到在n年后向上三角形的个数
2 写出前面的几个数F(0) = 1 , F(1) = 3 , F(2) = 10 , F(3) = 36 , F(4) = 136
通过前面几项我们可以找到通项公式F[n] = 4*F[n-1]-2^(n-1)
那么我们通过够找矩阵
| 4 -1 | * | F(n-1) | = | F(n) |
| 0 2 | | 2^(n-1) | | 2^n |
3 那么够造出矩阵之后我们直接利用矩阵快速幂，由于矩阵开始有负数，所以应该在取模的时候注意一下
第六题 hdu 2842 Chinese Rings
思路: 矩阵快速幂
分析:
1 题目的意思是给定n个环，和一些规则要把所有的环全部拆下最少需要的步数
2 题目规定如果要拆第n个环，那么第n-1个要挂着，n-2环要被拆下。那么我们设f(n)表示拆下前n个环的最少的步骤
那么考虑第n个环的情况，第n-1个环必须要挂着，n-2环要拆下，那么这一步就要f(n-2)，拆下第n个需要1步。然后只剩下第n-1个环，由于n-1环需要第n-2环挂着，所以我们需要把前n-2个环挂上去，所以需要f(n-2)，剩下n-1个需要拆下需要f(n-1)。那么总的需要f(n) = f(n-2)+1+f(n-2)+f(n-1) => f(n) = 2*f(n)+f(n-1)+1
3 接下来利用矩阵快速幂即可
第七题 hdu 2276 Kiki & Little Kiki 2
思路: 矩阵快速幂
分析:
1 题目给定一个01字符串然后进行m次的变换，变换的规则是：如果当前位置i的左边是1（题目说了是个圆，下标为0的左边是n-1），那么i就要改变状态0->1 , 1->0
比如当前的状态为100101那么一秒过后的状态为010111
2 假设0/1串的长度为n，保存在a数组，下标从0开始
根据上面的规则我们发现可以得出一秒过后的状态即为a[i] = (a[i]+a[i-1])%2 , 对于a[0] = (a[0]+a[n-1])%2
那么我们就可以就能够找到递推的式子
1 1 0 0.... a0 a1
0 1 1 0... * a1 = a2
..........1 1 ..... .....
1 0 0.....1 an-1 a0
3 但是我们最后要求的是a0 a1 .... an-1 ， 所以我们应该把矩阵的第一行和最和一行调换一下，然后进行m次的快速幂即可
4 由于最后的结果是mod2的结果，因此我们可以把所有的*和+运算全部改成&和^
第八题 hdu 2254 奥运
思路: 矩阵乘法
分析:
1 题目给定一个有向图，要求t1-t2天内v1-v2的路径的个数
2 假设有向图的邻接矩阵为A，那么A表示的是有向图中走一步能够到达哪些点的方案数，那么A^n表示的是走n步能够到达哪些点的方案数
3 根据离散数学里面的可达矩阵的性质，我们知道一个有向图的邻接矩阵的前n次幂的和即为可达矩阵，那么要求[t1-t2]之内的路径的条数，因为题目说了t1 = 0的时候为0。那么假设邻接矩阵为A，那么要求的就是A^(t1-1)+A^(t1)+...+A^(t2-1)，为什么是从t1-1开始呢，因为邻接矩阵本身代表走一步的结果
3 还有点的范围很大，边数很少，所以我们应该要进行离散化
4 但是数据量很大，对于具体的一组我们应该要事先求出具体的每一个矩阵，然后直接使用即可
第九题 hdu 3117 Fibonacci Numbers
思路: 矩阵快速幂
分析:
1 题目要求的是求F(n)中如果位数的个数大于8那么要输出前4四位和后四位，没有到8位的时候直接输出
2 根据题目的样例我们可以知道当n = 40的时候就超过8位了，所以我们可以知道n <= 39的时候直接去求F(n)，超过40的时候我们就要去求前4位和后四位
3 我们利用矩阵快速幂可以很快的求出后四位，但是前面四位就很困难了
下面看一下网上的解法
第十题 hdu 4686 Arc of Dream
思路: 矩阵快速幂
分析:
1 题目给定一个式子求和，那么根据题目给定的，我们可以求出an*bn = (an-1*Ax+Ay)*(bn-1*Bx+By) => an-1*bn-1*Ax*Bx+an-1*Ax*By+bn-1*Ay*Bx+Ay*By
2 那么我们根据上面的等式可以推出矩阵的乘法
3 那么我们要求的是AoD(n)相当于求左边矩阵的n次幂，然后利用结果乘上初始值
4 注意特判n为0的时候，结果为0。然后注意初始的值
第十一题 zoj 3690 Choosing number
思路: 递推+矩阵快速幂
分析;
1 题目的意思是有n个人和m个数和一个k，现在每个人可以选择一个数，但是要求如果相邻的两个人选择相同的数，那么这个数要大于k
2 假设F(n)表示前n个人第n个人选择的数大于k的个数，G(n)表示的是前n个人第n个人选择的数小于等于k的个数
那么F(n) = F(n-1)*(m-k)+G(n-1)*(m-k) , G(n) = F(n-1)*k+G(n-1)*(k-1) , 那么最后的结果就是F(n)+G(n);
那么我们可以构造出矩阵
| m-k m-k| | F(n-1) | | F(n) |
| k k-1| * | G(n-1) | => | G(n) |
那么初始值F(1) = m-k , G(1) = k