矩阵和线性方程组

矩阵运算,本质上是一个线性变换,将一个列向量x\bm{x} 变换成另一个列向量b\bm{b}
Ax=b\bm{A}\bm{x} = \bm{b}

逆矩阵 矩阵求逆在算法中很少使用,但思想是比较直观的
对于Ax=b\bm{Ax} = \bm{b}A1Ax=A1b\bm{A}^{-1} \bm{Ax} = \bm{A}^{-1} \bm{b}A1A=I\bm{A}^{-1} \bm{A} = \bm{I}
那么有x=A1b\bm{x} = \bm{A}^{-1} \bm{b}

矩阵可逆,当且仅当所有行向量线性无关,可化为行阶梯形矩阵

高斯消元

按照一般代数学知识,作增广矩阵后,化为行阶梯形矩阵 (REF)
i[0,n1]\forall i \in [0, n-1]Ai,nA_{i, n} 即为xix_i 的值

  • 列主元
    当前正在处理第ii 行,用第ii 行依次消去第[i+1n1][i+1\cdots n-1]
    需要保证的是Ai,i0A_{i, i} \neq 0,为了提高数值稳定性
    找到一个r>ir > i 并且绝对值最大的Ar,iA_{r, i},然后交换第rr 行与第ii

  • 消元,用第ii 行依次消去第k[i+1n1](k>i)k \in [i+1 \cdots n-1] \quad (k > i)
    kk 行所有列元素j[0,n1]\forall j \in [0, n-1]

    Ak,j=fAi,j, f=Ak,iAi,iAk,j=Ak,iAi,iAi,j\begin{aligned} A_{k, j} &-= f \cdot A_{i, j}, \ f = \frac{A_{k, i}}{A_{i, i}} \\ A_{k, j} &-= \frac{A_{k, i}}{A_{i, i}} \cdot A_{i, j} \end{aligned}

    为了保证精度,上式用右边的Ak,iA_{k, i} 来更新Ak,jA_{k, j},要保证Ak,iA_{k, i} 不会过早被破坏
    只要从 for j=ni\forall \ \textbf{for} \ j = n \to i 逆序枚举即可

    1
    2
    3
    4
    5
    for (int j = n; j >= i; j--) {
    for (int k = i+1; k < n; k++) {
    A[k][j] -= A[k][i] / A[i][i] * A[i][j];
    }
    }
  • 回代过程,化为若而当标准型
    在若而当标准型中,可以直接得到xi=Ai,n/Ai,ix_i = A_{i, n} / A_{i, i}
    化为若而当标准型,对于第ii 行,消去第j[i+1n1]j \in [i+1 \cdots n-1]

    • 如果令for i=n10\textbf{for} \ \forall i = n-1 \to 0 开始化为若而当标准型,要消去第j[i+1n1]j \in [i+1 \cdots n-1]
      于此同时j>ij > i 的列已经满足若而当标准型,并且Aj,nAj,n/Aj,jA_{j, n} \leftarrow A_{j, n} / A_{j, j}
      对于j>ij > i,此时xj=Aj,nx_j = A_{j, n}
    • 对于第ii 行,j>i, xjj > i, \ x_j 的系数为Ai,jA_{i, j},代入移项
      for j[i+1n1]\textbf{for} \ \forall j \in [i+1\cdots n-1]
      Ai,n=Aj,nAi,j\quad A_{i, n} -= A_{j, n} \cdot A_{i, j}
      之后令Ai,nAi,n/Ai,iA_{i, n} \leftarrow A_{i, n} / A_{i, i}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void gauss(double A[][maxn]) {
int i, r;
for (i = 0; i < n; i++) {
// swap
r = i;
for (int j = i+1; j < n; j++) {
if (fabs(A[j][i]) > fabs(A[r][i])) r = j;
}
if (r != i) for (int j = 0; j <= n; j++) swap(A[r][j], A[i][j]);

// eliminate
for (int j = n; j >= i; j--) {
for (int k = i+1; k < n; k++)
A[k][j] -= A[k][i] / A[i][i] * A[i][j];
}

// Jordan solution
for (int i = n-1; i >= 0; i--) {
for (int j = i+1; j < n; j--) A[i][n] -= A[i][j] * A[j][n];
A[i][n] /= A[i][i];
}
}
}

矩阵工具的应用

矩阵快速幂

Recurrences

首先根据递推关系构造矩阵

f(n)=a1f(n1)+a2f(n2)++adf(nd)f(n1)=a1f(n2)++ad1f(nd)+adf(n(d+1))\begin{aligned} f(n) &= a_1f(n-1) + &&a_2f(n-2) + \cdots + a_df(n-d) \\ f(n-1) &= &&a_1f(n-2) + \cdots + a_{d-1}f(n-d) + a_df(n-(d+1)) \end{aligned}

加上恒等式f(n1)=f(n1),f(n2)=f(n2)f(n-1) = f(n-1), f(n-2) = f(n-2) \cdots

可以构造矩阵如下

Fn=(f(n)f(n1)f(n2)f(nd))Fn1=(f(n1)f(n2)f(nd))\bm{F}_n = \begin{pmatrix} f(n) \\ f(n-1) \\ f(n-2) \\ \vdots \\ f(n-d) \end{pmatrix} \quad \bm{F}_{n-1} = \begin{pmatrix} f(n-1) \\ f(n-2) \\ \vdots \\ f(n-d) \end{pmatrix}

Fn=AFn1=(a1a2a3ad1000100001)(f(n1)f(n2)f(nd))\bm{F}_n = \bm{A}\bm{F}_{n-1} = \begin{pmatrix} a_1 & a_2 & a_3 &\cdots & a_d \\ 1 & 0 & 0 &\cdots & \vdots \\ 0 & 1 & 0 &\cdots & \vdots \\ \vdots &\vdots &\vdots & \ddots & \vdots \\ 0 & 0 & 0 &\cdots &1 \end{pmatrix} \begin{pmatrix} f(n-1) \\ f(n-2) \\ \vdots \\ f(n-d) \end{pmatrix}

其中Fn((d+1)×1),Fn1(d×1),A((d+1)×d)\bm{F}_n((d+1) \times 1), \bm{F}_{n-1}(d \times 1), \bm{A}((d+1) \times d),经过迭代后

F(d)=(f(d)f(d1)f(1))F(n)=AndF(d)\bm{F}(d) = \begin{pmatrix} f(d) \\ f(d-1) \\ \vdots \\ f(1) \end{pmatrix} \quad \bm{F}(n) = \bm{A}^{n-d} \bm{F}(d)

要求F(n)\bm{F}(n),进行矩阵幂运算后,执行矩阵乘法,得到结果矩阵为F\bm{F}F0,0\bm{F}_{0, 0} 即为所求

特殊情况,对于dnd \geqslant n 的情况如何处理?

F=AF0(f(d)f(d1)f(n))=A(f(d)f(d1)f(1))\bm{F} = \bm{A}\bm{F}_0 \Longrightarrow \begin{pmatrix} f(d) \\ f(d-1) \\ \vdots \\ f(n) \\ \vdots \end{pmatrix} = \bm{A}\begin{pmatrix} f(d) \\ f(d-1) \\ \vdots \\ f(1) \end{pmatrix}

由此F\bm{F}f(d0),f(d1),f(dk)f(d-0), f(d-1), \cdots f(d-k)F0\bm{F}_0 的第0,1,k0, 1, \cdots k 行对应
dk=n, k=dnd-k = n, \ k = d-n,由此F0(dn,0)\bm{F}_0(d-n, 0) 即为答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

const int maxn = 15 + 5;
typedef vector<vector<ll> > Matrix;
int d, n, mod;

Matrix matrix_mul(const Matrix &A, const Matrix &B) {
int _n = A.size(), _m = B[0].size();
Matrix res(_n, vector<ll> (_m, 0));

for (int i = 0; i < _n; i++) {
for (int j = 0; j < _m; j++)
for (int k = 0; k < (int)A[0].size(); k++)
res[i][j] = (res[i][j] + A[i][k] * B[k][j]) % mod;
}

return res;
}

Matrix matrix_pow(const Matrix &A, int exp) {
int sz = A.size();
Matrix I(sz, vector<ll>(sz, 0));
for (int i = 0; i < sz; i++) I[i][i] = 1;

Matrix res = I, B = A;
while (exp) {
if (exp & 1) res = matrix_mul(res, B);
B = matrix_mul(B, B);
exp >>= 1;
}
return res;
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d%d", &d, &n, &mod) == 3 && d) {
// init
// get data
Matrix A(d, vector<ll>(d, 0));
Matrix F(d, vector<ll>(1, 0));

for (int i = 0; i < d; i++) {
int x;
scanf("%d", &x);
A[0][i] = x;
}
for (int i = 1; i < d; i++) A[i][i-1] = 1;
for (int i = d-1; i >= 0; i--) scanf("%d", &F[i][0]);

// solve
if (n <= d) {
printf("%lld\n", F[d-n][0]);
continue;
}
Matrix res = matrix_mul(matrix_pow(A, n-d), F);
printf("%lld\n", res[0][0]);
}
}

循环矩阵和变换

Cellular Automation
构造变换矩阵A\bm{A}A(n×n)\bm{A}(n \times n)
对于第ii 行,Ai,i=1\bm{A}_{i, i} = 1,对于任意的j\forall jmin(ji,nji)d\min(|j-i|, n-|j-i|) \leqslant d
满足Ai,j=1\bm{A}_{i, j} = 1,举个例子,如果d=1d = 1,那么有

A=(11001111000111011001)\bm{A} = \begin{pmatrix} 1 & 1 & 0 & \cdots & 0 & 1 \\ 1 & 1 & 1 & \cdots & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & \cdots \\ & \vdots \\ 1 & 1 & 0 & \cdots & 0 & 1 \end{pmatrix}

下一行都是上一行的循环右移

v0\bm{v}_0为初始矩阵,经过kk 次变换后,v=Akv0\bm{v} = \bm{A}^k \bm{v}_0
循环矩阵只要知道第一行,可以推出任意一行,于是矩阵乘法可以优化,每次只要求出变换后的第一行即可

for i[0,n), j:A0,i=j=0n1A0,jBj,i,  Bj,i=B0[(ij+n)modn]\begin{aligned} \textbf{for} \ \forall i \in [0, n), \ &\forall j :\\ &A_{0, i} = \sum_{j = 0}^{n-1} A_{0, j} \cdot B_{j, i}, \ \ B_{j, i} = B_0[(i - j+n) \bmod n] \end{aligned}

B0B_0 存储第一行的初始向量,Bj,i\bm{B}_{j, i}B0,i\bm{B}_{0, i} 循环右移jj 位形成的
所以Bj,i=B0[(ij+n)modn]\bm{B}_{j, i} = B_0[(i-j+n) \bmod n],这样只需要O(n2)O(n^2) 时间复杂度计算矩阵乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
typedef vector<vector<ll> > Matrix;
int n, m, d, k;
Matrix A;
vector<ll> V;

Matrix mul(const Matrix &A, const Matrix &B) {
int _n = A.size(), _m = B[0].size();
Matrix C(_n, vector<ll> (_m, 0));
for (int i = 0; i < _m; i++) {
for (int j = 0; j < _m; j++)
C[0][i] = (C[0][i] + A[0][j] * B[j][i]) % m;
}
for (int i = 1; i < _n; i++) {
for (int j = 0; j < _m; j++)
C[i][j] = C[i-1][(j-1+n)%n];
}
return C;
}

Matrix pow(const Matrix &A, int exp) {
Matrix res(A.size(), vector<ll> (A[0].size(), 0));
for (int i = 0; i < res.size(); i++) res[i][i] = 1;
Matrix B = A;
while (exp) {
if (exp & 1) res = mul(res, B);
B = mul(B, B);
exp >>= 1;
}
return res;
}

void clear() {
V = vector<ll> (n, 0);
A = Matrix(n, vector<ll> (n, 0));
}

void calc(const Matrix &A) {
vector<ll> res(n, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
res[i] = (res[i] + A[i][j] * V[j] % m) % m;
}
printf("%lld", res[0]);
for (int i = 1; i < res.size(); i++) printf(" %lld", res[i]);
printf("\n");
}

int main() {
freopen("cell.in", "r", stdin);
freopen("cell.out", "w", stdout);
while (scanf("%d%d%d%d", &n, &m, &d, &k) == 4) {
// init
clear();

// data
for (int i = 0; i < n; i++) scanf("%lld", &V[i]);
for (int i = 0; i < n; i++) A[i][i] = 1;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= d; j++) A[i][(i+j+n)%n] = A[i][(i-j+n)%n] = 1;
}

// calc
Matrix T = pow(A, k);
calc(T);
}
}

马尔可夫问题

Gauss-Jordan消元
在 Gauss 消元法的基础上,可以省略掉回代过程,此时需要把矩阵化为对角阵

化为 Jordan 标准型

  • for i=1n\textbf{for} \ \forall i = 1 \to n
    \quad[i+1,n][i+1, n] 中选出第rr 行,使得Ar,iA_{r,i} 最大,swap(Ar,,Ai,)\bold{swap}(A_{r, \cdots}, A_{i, \cdots})
    \quad 基于第ii 行,消去所有kik \neq i 的行
     for ki,for j=n downto i\quad \ \textbf{for} \ \forall k \neq i, \quad \textbf{for} \ \forall j = n \ \textbf{downto} \ i
    \quad\quad\quadA(k,j)=A(k,i)/A(i,i)A(i,j)A(k, j) -= A(k, i) / A(i, i) \cdot A(i, j)
    \quadj<ij < i 的列Ai,j=0A_{i, j} = 0,不影响最终结果)

UVA10828
如果把节点uu 的出度记为dud_u,那么对于节点ii,其期望执行的次数记为xix_i

xi=upre(i)xudux_i = \sum_{u \in \text{pre}(i)} \frac{x_u}{d_u}

pre(i)\text{pre}(i)ii 的前驱节点

由此可以根据有向图列出期望线性方程,求解出xux_u,即为节点uu 的期望执行次数
但这样做会出现一些问题,有可能求出来的xux_u 是特殊的
可能uu 期望执行次数为00,也有可能为\infty

解决的方法很简单,只要使用Gauss-Jordan来避免回代过程,最后
xi=A(i,n)/A(i,i)x_i = A(i, n) / A(i, i)

  • 如果消元之后,A(i,i)=0 and A(i,n)0A(i, i) = 0 \ \textbf{and} \ A(i, n) \neq 0,此时ii 节点xi=+x_i = +\infty
    A(i,i)=0 and A(i,n)=0A(i, i) = 0 \ \textbf{and} \ A(i, n) = 0,那么xi=0x_i = 0
    xix_i 有限并且唯一,那么第ii 行除了A(i,i), A(i,n)A(i, i), \ A(i, n) 以外所有数均为00
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

typedef vector<vector<double> > Matrix;
const int maxn = 100 + 10;
const double eps = 1e-8;
int n, deg[maxn], Inf[maxn];
vector<int> pre[maxn];
Matrix A;

void build() {
for (int i = 0; i < n; i++) {
A[i][i] = 1;
for (auto u : pre[i]) A[i][u] -= 1.0 / deg[u];
if (i == 0) A[i][n] = 1;
}
}

void gauss_jordan() {
int i, r;
for (i = 0; i < n; i++) {
r = i;
for (int j = i+1; j < n; j++) {
if (fabs(A[j][i]) > fabs(A[r][i])) r = j;
}
if (fabs(A[r][i]) < eps) continue;
if (r != i) for (int j = 0; j <= n; j++) swap(A[r][j], A[i][j]);

// elimination
for (int k = 0; k < n; k++) if (k != i) {
for (int j = n; j >= i; j--) A[k][j] -= A[k][i] / A[i][i] * A[i][j];
}
}
}

void solve() {
memset(Inf, 0, sizeof Inf);
for (int i = n-1; i >= 0; i--) {
if (fabs(A[i][i]) < eps && fabs(A[i][n]) > eps) Inf[i] = 1;
for (int j = i+1; j < n; j++)
if (fabs(A[i][j]) > eps && Inf[j] == 1) Inf[i] = 1;
}

int q, u;
scanf("%d", &q);
while (q--) {
scanf("%d", &u);
u--;
double res = 0;
if (Inf[u]) printf("infinity\n");
else {
res = fabs(A[u][u]) < eps ? 0.0 : A[u][n] / A[u][u];
printf("%.3lf\n", res);
}
}
}

void init() {
memset(deg, 0, sizeof deg);
for (int i = 0; i < maxn; i++) pre[i].clear();
A = Matrix(n, vector<double>(n+1, 0));
}

int main() {
freopen("input.txt", "r", stdin);
int cas = 0;
while (scanf("%d", &n) == 1 && n) {
// init
printf("Case #%d:\n", ++cas);
init();

// get data
int a, b;
while (scanf("%d%d", &a, &b) == 2 && a) {
// a->b
a--, b--;
deg[a]++, pre[b].push_back(a);
}
// get matrix
build();

// gauss-jordan
gauss_jordan();

// solve
solve();
}
}

异或方程组的高斯消元

可以将该算法拓展到一般的代数系统中,比如线性方程组的代数系统扩展为模pp 的剩余系Zp\mathbb{Z}_{p}

Square
题意大致是给定nn 个数,从中选出一个或者多个,使得所选出的整数乘积是完全平方数

不含有大于500500 的素因子,很容易想到唯一分解定理
以样例来看,对于{4,6,10,15}\{4, 6, 10, 15\},唯一分解所用到的素因子为{2,3,5}\{2, 3, 5\}
观察幂指,根据幂指来构造向量如下

4=223050(2,0,0)6=213150(1,1,0)10=213051(1,0,1)15=203151(0,1,1)\begin{aligned} 4 = 2^2 \cdot 3^0 \cdot 5^0 \quad \quad &(2, 0, 0) \\ 6 = 2^1 \cdot 3^1 \cdot 5^0 \quad \quad &(1, 1, 0) \\ 10 = 2^1 \cdot 3^0 \cdot 5^1 \quad \quad &(1, 0, 1) \\ 15 = 2^0 \cdot 3^1 \cdot 5^1 \quad \quad &(0, 1, 1) \end{aligned}

原数组为{a1,a2,an}\{a_1, a_2, \cdots a_n\},用xix_i 表示选 or 不选aia_i 这个数
状态数组为{x1,x2,xn}\{x_1, x_2, \cdots x_n\}

那么上述问题实际上是要考虑

(x1,x2,x3,x4)(200110101011)(x_1, x_2, x_3, x_4) \begin{pmatrix} 2 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}

要为完全平方数,必须满足

{2x1+x2+x3+0x40(mod2)0x1+x2+0x3+x40(mod2)0x1+0x2+x3+x40(mod2)\begin{cases} 2x_1 + x_2 + x_3 + 0x_4 \equiv 0 (\bmod 2) \\ 0x_1 + x_2 + 0x_3 + x_4 \equiv 0 (\bmod 2) \\ 0x_1 + 0x_2 + x_3 + x_4 \equiv 0 (\bmod 2) \end{cases}

上述问题实际上是Z2\mathbb{Z}_2 剩余系中的矩阵运算
注意到形如2xi2x_i 的数,总是能够写成完全平方数,也就是说,2xi0(mod2)2x_i \equiv 0(\bmod 2)
偶数在模22 剩余系中的运算结果总是00,这启发我们用异或\oplus 运算

{x2x3=0x2x4=0x3x4=0\begin{cases} x_2 \oplus x_3 = 0 \\ x_2 \oplus x_4 = 0 \\ x_3 \oplus x_4 = 0 \end{cases}

于是可以这样构造算法,为了符合一般矩阵运算的写法

(x1,x2,x3,x4)(200110101011)(x_1, x_2, x_3, x_4) \begin{pmatrix} 2 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}

取一个转置变为

Ax=(211001010011)(x1x2x3x4)(0000)(mod2)\bm{Ax} = \begin{pmatrix} 2 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} \equiv \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} (\bmod 2)

具体来说

  • {a1,a2an}\{a_1, a_2 \cdots a_n\} 唯一分解,假设所用到的素数为{p1,p2,pm}\{p_1, p_2, \cdots p_m\}
    构造m×nm \times n 的矩阵A\bm{A},如果aia_i 含有素因子pjp_j,那么令A(j,i)=1A(j,i) \oplus = 1
    注意如果aia_ipjp_j 的幂指为kk,需要A(j,i)=1A(j, i) \oplus = 1 操作kk
  • 对异或矩阵执行高斯消元,并且求出矩阵的秩为rr,矩阵的自由变量为nrn-r
    每一个自由变量有22 种取值,选 or 不选,所以答案为2nr2^{n-r}

异或方程组的高斯消元比较简单

  • 假设当前正在处理第ii 行第jj 列,首先要找到A(r,j)0A(r, j) \neq 0 的第rr
    并且将第rr 行与第ii 行交换
  • 消元之后第ii 行的第一个非00 列为第jj
    并且对于所有u>iu > i 的行,它的第jj 列都为00
    对于u[i+1,n]u \in [i+1, n] 的行,用第ii 行来消去它
    即对于列k[i,n]k \in [i, n]对应地令A(u,k)=A(i,k)A(u, k) \oplus = A(i, k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
const int maxn = 500 + 10;
typedef vector<vector<int> > Matrix;
int tot = 0, n;
Matrix A;

vector<int> primes;

void get_primes(int m) {
primes.clear();

bool st[maxn];
memset(st, 0, sizeof st);

for (int i = 2; i <= m; i++) {
if (st[i]) continue;
primes.push_back(i);
for (int j = i; j <= m; j += i) st[j] = 1;
}
}

int gauss_jordan(Matrix &A, int m, int n) {
// m * n
int i = 0, j = 0;
for (; i < m && j <= n; j++) {
// find r, A(r, j) != 0
int r = i;
for (int k = i; k < m; k++) if (A[k][j]) {
r = k; break;
}
if (A[r][j] == 0) continue;
if (r != i) for (int k = 0; k <= n; k++) swap(A[r][k], A[i][k]);

// elimination
for (int u = i+1; u < m; u++) if (A[u][j]) {
for (int k = i; k <= n; k++) A[u][k] ^= A[i][k];
}
i++;
}
return i;
}

void init() {
tot = 0;
A = Matrix(maxn, vector<int>(maxn, 0));
}

int main() {
freopen("input.txt", "r", stdin);
int cas;
cin >> cas;
get_primes(500);

while (cas--) {
init();

scanf("%d", &n);
for (int i = 0; i < n; i++) {
ll x; scanf("%lld", &x);

for (int j = 0; j < primes.size(); j++) {
while (x % primes[j] == 0) {
x /= primes[j], A[j][i] ^= 1;
tot = max(tot, j);
}
}
}

int r = gauss_jordan(A, tot+1, n);
ll res = (1ll << (n-r)) - 1;
printf("%lld\n", res);
}
}