Ma Trận Đảo · canuc80k6303

Cho ma trận vuông $A$ cấp $n$ , các phần tử thuộc trường modulo $1000000007$ . Hãy tìm ma trận $B$ sao cho

A \cdot B = B \cdot A = I (mod 1000000007),

trong đó $I$ là ma trận đơn vị. Nếu không tồn tại ma trận như vậy, cần báo rằng $A$ không khả nghịch.

Dòng đầu chứa số nguyên $n$ .
Mỗi trong $n$ dòng tiếp theo chứa $n$ số nguyên. Số thứ $j$ trên dòng thứ $i$ là $a_{i, j}$ .

Nếu $A$ khả nghịch, in $n$ dòng, mỗi dòng $n$ số nguyên trong đoạn $[0, 1000000007)$ , tạo thành ma trận $A^{- 1}$ . Các số trên cùng một dòng cách nhau bởi một dấu cách.
Nếu $A$ không khả nghịch, in một dòng No Solution.

Test 1

Input

2
1 2
3 5

Output

1000000002 2
3 1000000006

Giải thích: Nhân ma trận đã cho với ma trận được in ra thu được ma trận đơn vị modulo $1000000007$ , nên đây chính là nghịch đảo của $A$ .

Ý tưởng: Ghép ma trận thành [A | I]. Ở cột c, tìm một hàng từ c trở xuống có phần tử khác 0, đổi lên làm pivot, nhân hàng với nghịch đảo modulo của pivot rồi khử cột đó ở mọi hàng khác. Nếu không tìm được pivot thì rank(A)<n, vì vậy nghịch đảo không tồn tại. Khi đủ n pivot, nửa trái trở thành I; mọi phép biến đổi hàng đã tác động đồng thời lên nửa phải nên nửa phải là A^{-1}.
Ý tưởng: Modulo 1 000 000 007 là số nguyên tố, do đó nghịch đảo của pivot v≠0 là v^(MOD-2) mod MOD. Thuật toán dùng O(n^3) thời gian và O(n^2) bộ nhớ.