矩阵乘法题目总结

矩阵乘法题目总结 By Matru sh 关于矩阵乘法请见：矩阵乘法[Matrix Multiply]，以下是我最近做的一些关于矩阵乘法的题目，来源是一些经典题以及HDU shǎ 崽大牛总结的矩阵乘法的题目[1]、[2]和开设的矩阵乘法DIY Contest。 题目不一定按难度排列： PKU3070-Fibonacci：最经典的递推题，由 F[n] = F[n-1] + F[n-2]，常系数递推式右边有两项，所以向量和矩阵的规格都为 2。容易如下递推： 矩阵二分快速幂计算 Ak 即可。 HDU3117-Fibonacci Numbers：后四位的同上题，前四位用公式： HDU2855-Fibonacci Check-up：多校联合赛的一道题，那个公式化简了半天没化出来，最后迫于无奈暴力了一下，发现规律了：只要知道如下结论就和最上面那题一样了： HDU1575-Tr A：Tr A 表示方阵A 的迹（主对角线元素之和），求 Tr(Ak) % 9973。 由于k 最大有10^9，所以只能用矩阵二分快速幂得到Ak，最后求和即可。 PKU3233-Matrix Power Series：求Sn = A + A2 + A3 + … + An。 首先我们能矩阵二分快速幂计算出 Ak，那么我们对 S 再进行二分： 当 n % 2 != 0 则计算 An+S(n-1)，当 n % 2 == 0 时计算 S(n/2)*(An/2+E)，这样就可以在 log(n)的时间里算出 Sn 代码： Mat sum(int x)//A^1+A^2+...+A^x { if (x == 1) return A; if (x & 1) return (A^x)+sum(x-1); else return sum(x/2)*((A^(x/2))+E); } HDU2604-Queuing：推出递推式构造矩阵： HDU1757-A Simple Math Problem：按题意所给的函数递推构造矩阵： HDU2256-Problem of Precision：按题目所给的式子算出前几项找规律，不知道有没有更好的数学证明： HDU2294-Pendant：题意求长为n 的挂件一定包含 k 种颜色的方案数，应该算DP+矩阵优化，第一次这么做竟然 1Y，很高兴： HDU2276-Kiki & Little Kiki 2：按shǎ 崽大牛的话说是隐藏比较深的题，不过在纸上小推了一下就找到了规律：因为当某个位的左边是1 时该位 0->1，1->0，左边是0 时该位 0->0，1->1，不难发现当考虑线性结构的话有 f[i] = (f[i] + f[i-1]) % 2，而题目是环形结构，只需对两端的点考虑特殊情况即可：f[i] = (f[i] + f[(n+i-2) % n + 1]) % 2： FZU1692-Key problem：A(i)=A(i) + L*A(i+n-1)%n + R*A(i+1)%n 这种环形权值改变问题都可以和上题一样构造矩阵来解： ☆以上两题的矩阵都有一个特点就是...