matrix

题目描述

该题目需要完成一个简易的矩阵计算器, 该计算器需要对输入的 1 个或 2 个整数矩阵完成一次运算并输出结果.

所需要完成的计算类型为:

矩阵相加 (ADD);
矩阵相减 (SUB);
矩阵数乘 (SCAMUL);
矩阵向量乘 (VECMUL);
矩阵乘法 (MUL);
矩阵转置 (TRANS);
方阵的幂 (POW);
方阵的行列式 (DET).

保证所有输入是有效的, 不需要做矩阵大小是否匹配等判断.

输入格式

第 1 行为运算类型, 即上述括号中的字符串.

第 2 行为矩阵参数, 具体来说:

矩阵相加 (ADD): r c , 表示两个等大矩阵的行列数.
矩阵相减 (SUB): r c , 表示两个等大矩阵的行列数.
矩阵数乘 (SCAMUL): r c s , 表示矩阵的行列数, 以及数乘所用的数.
矩阵向量乘 (VECMUL): r c, 表示矩阵的行列数.
矩阵乘法 (MUL): r l c, 表示第一个矩阵大小为 $r \times l$ , 第二个矩阵大小为 $l \times c$ .
矩阵转置 (TRANS): r c, 表示矩阵的行列数.
方阵的幂 (POW): n k , 表示方阵的阶数, 以及幂次.
方阵的行列式 (DET): n , 表示方阵的阶数.

接下来的若干行为矩阵的元素, 以矩阵乘法的输入为例: 接下来的 r 行, 每行有 l 个整数, 用空格隔开; 再接下来的 l 行, 每行有 c 个整数, 用空格隔开.

输出格式

如果结果为矩阵, 直接仿照输入的格式输出矩阵元素即可;
如果结果为向量, 使用列向量格式输出, 即 $r \times 1$ 的矩阵;
如果结果为数字, 直接输出即可.

对于方阵的幂运算, 由于幂次可能过大, 输出的矩阵元素需要模 1000000007 ($10^9 + 7$) , 其它运算不需要此操作.

样例

此样例即为测试点 1.

样例输入

ADD
5 5
15 -86 -45 10 29 
99 -62 14 -37 53 
4 -36 -47 45 -99 
-11 24 78 58 4 
-26 -71 -26 86 94 
-14 80 -80 14 25 
35 53 -85 -17 -11 
-25 83 85 12 52 
-48 53 81 99 -89 
-72 59 4 70 -80

样例输出

1 -6 -125 24 54 
134 -9 -71 -54 42 
-21 47 38 57 -47 
-59 77 159 157 -85 
-98 -12 -22 156 14

说明

测试点:

对于前 8 个测试点, 即为上述的 8 种运算, 只考察实现的正确性, 对时间复杂度要求不高.
对于后 2 个测试点, 分别为方阵的幂与方阵的行列式, 对时间复杂度有一定的要求.

数据规模:

对于前 6 种运算: 0 < r, c, l <= 3000.
对于方阵的幂运算: 0 < n <= 100 , 0 < k < 1000000000000 ($10^{12}$) .
对于方阵的行列式: 0 < n <= 12 .
所有输入的矩阵元素 a_ij 满足 -100 <= a_ij <= 100.

提示

对于方阵的幂运算, 当幂次较大时, 直接反复乘矩阵的复杂度是 $O(n^3 k)$ 的; 你应该需要找到一个合适的策略, 把复杂度降到 $O(n^3 \log k)$ .
对于方阵的行列式, 直接使用行列式的展开式, 复杂度是 $O(n!)$ 的, 你应该要找到一个合适的策略, 把复杂度降到 $O(n^3)$ .
虽然所有矩阵输入与输出的结果都在 int 范围内, 但 int 可能不能满足计算的需求.

Universal Online Judge

UOJ

#6. matrix