线代（高斯消元法、线性基）

一、高斯消元法

1、将问题转化为矩阵方程，再转化为多个n元一次方程，从而使用高斯消元法

使用高斯消元法的关键在于构造增广矩阵

2、需求解的未知数可能是很多类型，例如浮点型、01型

（1）、异或类型解

bitset<maxn>a[maxn];        //a数组代表增广矩阵的系数，常数项在最后
int ans[maxn], Free[maxn], cnt;    //ans代表最后方程组的解，Free和cnt是自由元
int Gauss(int equ, int var)    //equ个方程组，var个位置数
{
	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）、浮点类型解

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）、整数类型解

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）、模线性方程组

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;
}

二、线性基

1、线性基是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数

2、线性基的构造

int d[maxn];
void add(ll x)
{
	for (int i = 60; i >= 0; i--)
	{
		if (x & (1ll << i))//注意，如果i大于31，前面的1的后面一定要加ll
		{
			if (d[i])x ^= d[i];
			else
			{
				d[i] = x;
				break;//插入成功就退出
			}
		}
	}
}