#P18426. Matrix Inverse

Matrix Inverse

Matrix Inverse

给定素数 pp,一个 n×nn\times n 的矩阵的所有元素都是 00 到 p−1p-1 之间的整数。矩阵 MM 的第 ii 行、第 jj 列元素记为 Mi,jM_{i,j}(1≤i,j≤n1\le i,j\le n)。本题固定

p=1 000 000 007.p=1\,000\,000\,007.

如果对所有 1≤i,j≤n1\le i,j\le n,

∑ℓ=1nAi,ℓBℓ,j(modp)\sum_{\ell=1}^{n} A_{i,\ell}B_{\ell,j}\pmod p

在 i=ji=j 时等于 11,在 i≠ji\ne j 时等于 00,就称 BB 是 AA 的逆矩阵。

给定矩阵 AA,保证其逆矩阵 BB 存在且唯一。你的任务是求出 BB。为了降低难度,还会给你一个矩阵 CC,它与所求的 BB 至多有十二个元素不同。请输出 CC 中所有需要修改的元素及其在 BB 中的正确值。

输入格式

第一行包含一个整数 nn(1≤n≤20001\le n\le2000),表示矩阵的阶数。

接下来 nn 行描述矩阵 AA。其中第 ii 行包含 nn 个整数,第 jj 个是 Ai,jA_{i,j}(0≤Ai,j≤p−10\le A_{i,j}\le p-1)。保证 AA 的逆矩阵存在且唯一。

再接下来 nn 行,以相同方式描述矩阵 CC,每个元素也在 00 到 p−1p-1 之间。保证满足 Bi,j≠Ci,jB_{i,j}\ne C_{i,j} 的不同位置 (i,j)(i,j) 的数量至多为十二。

输出格式

第一行输出一个整数 kk(0≤k≤120\le k\le12),表示需要修改的元素数。

接下来 kk 行,每行输出三个整数 xi,yi,wix_i,y_i,w_i(1≤xi,yi≤n1\le x_i,y_i\le n,0≤wi≤p−10\le w_i\le p-1),表示 Bxi,yi=wiB_{x_i,y_i}=w_i 且 Cxi,yi≠wiC_{x_i,y_i}\ne w_i。

必须按行号从小到大输出;行号相同时,按列号从小到大输出。按这些要求,正确输出是唯一的。若 k=0k=0,仅输出一行 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}.$$

所以给出的 CC 恰有两个元素需要修改。