Line generation (Gauss elimination method, linear basis)

One 、 Gauss elimination

1、 Turn the problem into a matrix equation , And then convert to multiple n The first-order equation of variables , Thus Gauss elimination method is used

The key of using Gauss elimination method is to construct augmented matrix

2、 The unknowns of the demand solution may be of many types , For example, floating point 、01 type

（1）、 XOR type solution

bitset<maxn>a[maxn];        //a The array represents the coefficients of the augmented matrix , The constant term is at the end 
int ans[maxn], Free[maxn], cnt;    //ans Represents the solution of the last set of equations ,Free and cnt Is a free element 
int Gauss(int equ, int var)    //equ Equations ,var Number of positions 
{
	int row, col, MaxRow;
	col = 0;
	for (row = 0; row < equ && col < var; row++, col++)
	{
		MaxRow = row;
		for (int i = row + 1; i < equ; i++)
		{
			if (abs(a[i][col]) > abs(a[MaxRow][col]))
				MaxRow = i;
		}
		if (MaxRow != row)
		{
			swap(a[row], a[MaxRow]);
		}
		if (a[row][col] == 0)
		{
			row--;
			Free[++cnt] = col;
			continue;
		}
		for (int i = row + 1; i < equ; i++)
		{
			if (a[i][col])
				a[i] ^= a[row];
		}
	}
	for (int i = row; i < equ; i++)
	{
		if (a[i][col])
			return -1;
	}
	if (row < var)
		return var - row;
	for (int i = var - 1; i >= 0; i--)
	{
		ans[i] = a[i][var];
		for (int j = i + 1; j < var; j++)
		{
			if (a[i][j])
				ans[i] ^= (a[i][j] && ans[j]);
		}
	}
	return 0;
}

（2）、 Floating point type solution

double a[maxn][maxn], ans[maxn];
int cnt, Free[maxn];

int Gauss(int equ, int var)
{
    for (int i = 0; i <= var; i++)
    {
        ans[i] = 0;
        Free[i] = 1;
    }
    int row, col, MaxRow;
    col = 0;
    for (row = 0; row < equ && col < var; row++, col++)
    {
        MaxRow = row;
        for (int i = row + 1; i < equ; i++)
        {
            if (fabs(a[i][col]) > fabs(a[MaxRow][col]))
                MaxRow = i;
        }
        if (MaxRow != row)
        {
            for (int i = row; i <= var; i++)
                swap(a[row][i], a[MaxRow][i]);
        }
        if (fabs(a[row][col]) < eps)
        {
            row--;
            continue;
        }
        for (int i = row + 1; i < equ; i++)
        {
            if (fabs(a[i][col]) > eps)
            {
                double temp = a[i][col] / a[row][col];
                for (int j = col; j <= var; j++)
                    a[i][j] -= a[row][j] * temp;
                a[i][col] = 0;
            }
        }
    }
    for (int i = row; i < equ; i++)
    {
        if (fabs(a[i][col]) > eps)
            return -1;
    }
    double temp;
    if (row < var)
    {
        for (int i = row - 1; i >= 0; i--)
        {
            int free_num = 0, idx;
            for (int j = 0; j < var; j++)
            {
                if (a[i][j] && Free[j])
                {
                    free_num++;
                    idx = j;
                }
            }
            if (free_num > 1)
                continue;
            temp = a[i][var];
            for (int j = 0; j < var; j++)
            {
                if (a[i][j] && j != idx)
                    temp -= a[i][j] * ans[j];
            }
            ans[idx] = temp / a[i][idx];
            Free[idx] = 0;
        }
        return var - row;
    }
    for (int i = var - 1; i >= 0; i--)
    {
        temp = a[i][var];
        for (int j = i + 1; j < var; j++)
        {
            if (a[i][j])
                temp -= a[i][j] * ans[j];
        }
        ans[i] = temp / a[i][i];
    }
    return 0;
}

（3）、 Integer type solution

int a[maxn][maxn];
int ans[maxn];
int Free[maxn];
int GCD(int a, int b)
{
	if (!b)
		return a;
	return GCD(b, a % b);
}
int LCM(int a, int b)
{
	return a / GCD(a, b) * b;
}
int Fabs(int x)
{
	if (x < 0)
		return -x;
	return x;
}
int Gauss(int equ, int var)
{
	for (int i = 0; i <= var; i++)
	{
		ans[i] = 0;
		Free[i] = 1;
	}
	int row, col, MaxRow;
	col = 1;
	for (row = 1; row <= equ && col < var; row++, col++)
	{
		MaxRow = row;
		for (int i = row + 1; i <= equ; i++)
		{
			if (Fabs(a[i][col]) > Fabs(a[MaxRow][col]))
				MaxRow = i;
		}
		if (MaxRow != row)
		{
			for (int i = row; i <= var; i++)
				swap(a[row][i], a[MaxRow][i]);
		}
		if (!a[row][col])
		{
			row--;
			continue;
		}
		for (int i = row + 1; i <= equ; i++)
		{
			if (a[i][col])
			{
				int lcm = LCM(Fabs(a[i][col]), Fabs(a[row][col]));
				int T1 = lcm / Fabs(a[i][col]);
				int T2 = lcm / Fabs(a[row][col]);
				if (a[i][col] * a[row][col] < 0)
					T2 = -T2;
				for (int j = col; j <= var; j++)
					a[i][j] = a[i][j] * T1 - a[row][j] * T2;
			}
		}
	}
	for (int i = row; i <= equ; i++)
	{
		if (a[i][col])
			return -1;
	}
	int temp;
	if (row < var)
	{
		return var - row;
	}
	for (int i = var - 1; i > 0; i--)
	{
		temp = a[i][var];
		for (int j = i + 1; j < var; j++)
		{
			if (a[i][j])
				temp -= a[i][j] * ans[j];
		}
		ans[i] = temp / a[i][i];
	}
	return 0;
}

（4）、 A system of modular linear equations

int a[maxn][maxn];
int Gauss(int equ, int var)
{
	int row, col = 0;
	for (row = 0; row < equ && col < var; row++, col++)
	{
		int MaxRow = row;
		for (int i = row + 1; i < equ; i++)
		{
			if (abs(a[i][col]) > abs(a[MaxRow][col]))
				MaxRow = i;
		}
		if (row != MaxRow)
		{
			for (int i = row; i <= var; i++)
				swap(a[row][i], a[MaxRow][i]);
		}
		if (!a[row][col])
		{
			row--;
			continue;
		}
		for (int i = row + 1; i <= equ; i++)
		{
			if (a[i][col])
			{
				int T = a[i][col] * q_pow(a[row][col], mod - 2, mod) % mod;
				for (int j = col; j <= var; j++)
					a[i][j] = (a[i][j] - a[row][j] * T % mod + mod) % mod;
			}
		}
	}
	for (int i = row; i <= equ; i++)
	{
		if (a[i][col])
			return -1;
	}
	if (row < var)
		return var - row;
	for (int i = var - 1; i >= 0; i--)
	{
		int temp = a[i][var];
		for (int j = i + 1; j < var; j++)
		{
			if (a[i][j])
			{
				temp -= a[i][j] * x[j];
				temp = (temp % mod + mod) % mod;
			}
		}
		x[i] = temp * q_pow(a[i][i], mod - 2, mod) % mod;
	}
	return 0;
}

Two 、 Linear base

1、 A linear basis is a set of numbers , And each sequence has at least one linear basis , Any number in the original sequence can be obtained by taking the exclusive or of several numbers in the linear base

2、 The construction of linear basis

int d[maxn];
void add(ll x)
{
	for (int i = 60; i >= 0; i--)
	{
		if (x & (1ll << i))// Be careful , If i Greater than 31, Ahead 1 Be sure to add the following ll
		{
			if (d[i])x ^= d[i];
			else
			{
				d[i] = x;
				break;// Insert successfully and exit 
			}
		}
	}
}