Skip to content

1312: Unique

题目

题目描述

饱受《高等代数》这门课折磨的天天希望你能够帮助他完成作业。在作业本上有$n$个大小都为$m\times m$的矩阵(方阵),它们依次排成一行,从$1$开始标号。定义$i$号矩阵$M_i$等价与$j$号矩阵$M_j$,当且仅当存在两个可逆矩阵$P$和$Q$,使得$M_i=PM_jQ$。当然,为了满足矩阵乘法条件,$P$和$Q$的大小都是$m\times m$(具体可以参考Wiki)。现在这一行矩阵,天天希望将连续本质相同的矩阵删减,留下相邻之间本质不同对的矩阵。具体来说,找到所有连续的互相等价的矩阵,保留最早出现的矩阵的编号,删除其他的编号。天天想要知道最后留下来的这些矩阵的标号是多少。

(提示)STL的算法库里有函数std::unique(),希望利用这个函数(具体可以参考C++_Reference),并且用Lambda表达式的形式传入函数指针。

注意

为了避免精度问题,我们在对$10^9+7$取模的意义下定义矩阵乘法和数乘,并且保证所有矩阵的元素都是整数。

输入格式

第一行两个整数$n$,$m$,分别表示矩阵个数和大小

接下来连续输入$n$个矩阵

每个矩阵输入$m\times m$个整数表示矩阵的元素

输出格式

第一行一个整数$n$,表示输出个数

第二行$n$个数,表示删除之后剩下的矩阵编号

样例输入

text 5 3 -1 2 -6 5 -2 0 -6 5 -1 -2 -2 1 1 -2 2 -2 1 -5 -1 6 6 0 0 0 1 -6 -6 5 0 0 4 0 0 4 0 0 0 0 0 0 0 0 0 0 0

样例输出

text 3 1 3 5

数据范围

满足,$n\le1000$,$m\leq30$,$-1000\leq矩阵元素\le1000$

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!