#Algo1004. 【模板】矩阵求逆

    ID: 190 远端评测题 1000ms 128MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>数论数学高斯消元乘法逆元luogu模板

【模板】矩阵求逆

题目描述

求一个 N×NN\times N 的矩阵的逆矩阵。答案对 109+7{10}^9+7 取模。

输入格式

第一行有一个整数 NN,代表矩阵的大小;

接下来 NN 行,每行 NN 个整数,其中第 ii 行第 jj 列的数代表矩阵中的元素 aija_{i j}

输出格式

若矩阵可逆,则输出 NN 行,每行 NN 个整数,其中第 ii 行第 jj 列的数代表逆矩阵中的元素 bijb_{i j},答案对 109+7{10}^9+7 取模;

否则只输出一行 No Solution

3
1 2 8
2 5 6
5 1 2
718750005 718750005 968750007
171875001 671875005 296875002
117187501 867187506 429687503
3
3 2 4
7 2 9
2 4 3
No Solution

提示

30%30 \% 的数据有 N100N\le 100
100%100 \% 的数据有 N400N\le 400,所有 0aij<109+70 \le a_{i j} < {10}^9 + 7