#P18426. Matrix Inverse
Matrix Inverse
Matrix Inverse
给定素数 ,一个 的矩阵的所有元素都是 到 之间的整数。矩阵 的第 行、第 列元素记为 ()。本题固定
如果对所有 ,
在 时等于 ,在 时等于 ,就称 是 的逆矩阵。
给定矩阵 ,保证其逆矩阵 存在且唯一。你的任务是求出 。为了降低难度,还会给你一个矩阵 ,它与所求的 至多有十二个元素不同。请输出 中所有需要修改的元素及其在 中的正确值。
输入格式
第一行包含一个整数 (),表示矩阵的阶数。
接下来 行描述矩阵 。其中第 行包含 个整数,第 个是 ()。保证 的逆矩阵存在且唯一。
再接下来 行,以相同方式描述矩阵 ,每个元素也在 到 之间。保证满足 的不同位置 的数量至多为十二。
输出格式
第一行输出一个整数 (),表示需要修改的元素数。
接下来 行,每行输出三个整数 (,),表示 且 。
必须按行号从小到大输出;行号相同时,按列号从小到大输出。按这些要求,正确输出是唯一的。若 ,仅输出一行 0。
原样例 1
输入:
2
1 1
0 2
1 2
3 500000004
输出:
2
1 2 500000003
2 1 0
原样例 2
输入:
3
0 1 0
0 0 1
1 0 0
0 0 1
1 0 0
0 1 0
输出:
0
原题说明
样例 1 中,
$$A=\begin{pmatrix}1&1\\0&2\end{pmatrix},\qquad B=\begin{pmatrix}1&500\,000\,003\\0&500\,000\,004\end{pmatrix}.$$所以给出的 恰有两个元素需要修改。