首页 > 代码库 > 矩阵总结

矩阵总结

2024-07-18 14:45:12   219人阅读


矩阵题目总结

题目来源参考了：http://blog.csdn.net/a601025382s/article/details/10251613


简单矩阵：

HDU 1575：http://acm.hdu.edu.cn/showproblem.php?pid=1575

题意：给定矩阵A， 求Tr(A^k) % 9973。 其中Tr为矩阵的迹 代码


常系数线性齐次递推

HDU 1005： http://acm.hdu.edu.cn/showproblem.php?pid=1005 

题意：f[n] = (A * f[n - 1] + B * f[n - 2]) % mod, f[1] = f[2] = 1, 给定A,B,n，求f[n]。 代码


HDU 1757：http://acm.hdu.edu.cn/showproblem.php?pid=1757

题意：If x < 10 f(x) = x. If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10) And ai(0<=i<=9) can only be 0 or 1 .现在给你k和m，求f(k) % m。解题报告


逆矩阵：

POJ 1166： http://poj.org/problem?id=1166

题意：9只钟表排成3 * 3的矩阵，每个钟只能指向上下左右四个位置，现在给你9种作用方式，每种可以使一些钟表的指针右转90度。现在使用这九种方式，使得所有钟表都朝上。求总作用次数最少的策略

思路：这道题之前用二进制枚举做过，每种作用方式四次一循环，所以暴力为：1 << 18。但如果作用方式变多一些，就不能这么做了。

可以采用逆矩阵来解这道题：

?把钟表和作用分别从1到9标号，则同余方程组可写为
?[C(i) +∑E(i,j) * M (j)] mod 4= 0 (i=1..9)
?其中C(i),M(j),E(i,j)分别表示第i个钟表的初始状态，第j种作用的次数，第j种作用是否拨动第i个钟表

?写成矩阵的形式
            ( C + E M ) mod 4 = 0          (*)
  我们所求为M的最小非负解M0=M mod 4
?显然，当k足够大时，方程
               C + E M’ = 4 * k
   的解也是 (*) 式的解，故
                 M0 =M’ mod 4
?由于E是与输入无关的系数矩阵，所以我们可以事先求出其逆矩阵E  ，则M  可以写成
         M  =( E   ( 4 * k – C ) ) mod 4
?这样，我们只需用另一段程序求出E  ，问题就可以在O(1)的时空内解决。

 具体看下面的链接：传送门（讲的非常详细）

代码：http://paste.ubuntu.com/7862915/ 



矩阵 + dp

POJ 3734：http://poj.org/problem?id=3734

题意：有一排砖，数量为N。现要将砖全部染上色，有红、蓝、绿、黄四种颜色。要求被染成红色和绿色的砖块数量必须为偶数，问一共有多少种染色方案。（由于答案较大，模10007）解题报告


POJ 3420： http://poj.org/problem?id=3420

题意：有一个 4 * N (1 ≤ N ≤ 10^9) 的矩形，用1 * 2 的木块去铺满它，问有多少种方法。答案可能很大，对 M 取模。 

思路：这道题目的难点在于dp，如何找到状态转移是突破点， （POJ 2411 的题解，有详细的解释）。可以写成一个16 * 16 的矩阵，然后再用矩阵快速幂即可。

代码：http://paste.ubuntu.com/7861188/


联系
我们