发表于
30 Jan 2019
总计
2187字
阅读时间
8分
CC BY 4.0
（除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
矩阵
1
| typedef array<array<ll, N>, N> Mat;
|
乘法和快速幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| Mat operator*(const Mat &a, const Mat &b)
{
Mat r;
for (int i = 0; i < r.size(); ++i)
for (int j = 0; j < r.size(); ++j)
for (int k = r[i][j] = 0; k < r.size(); ++k)
M.qadd(r[i][j], M.mul(a[i][k], b[k][j]));
return r;
}
Mat pow(Mat a, ll b)
{
Mat r;
for (int i = 0; i < r.size(); ++i)
for (int j = 0; j < r[i].size(); ++j)
r[i][j] = i == j;
for (; b; b >>= 1, a = a * a)
if (b & 1)
r = r * a;
return r;
}
|
行列式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| ll det(Mat a, int n)
{
ll ans = 1;
for (int i = 0; i < n; ++i)
{
for (int j = i + 1; j < n; ++j)
while (fabs(a[j][i]) > EPS)
{
ll t = a[i][i] / a[j][i];
for (int k = i; k < n; ++k)
a[i][k] -= t * a[j][k], swap(a[i][k], a[j][k]);
}
if (fabs(ans *= a[i][i]) < EPS)
return 0;
}
return ans;
}
|
高斯消元
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void GaussElimination(Mat &a, int n) //a为增广矩阵，要求n*n的系数矩阵可逆，运行结束后a[i][n]为第i个未知数的值
{
for (int i = 0, r; i < n; ++i)
{
for (int j = r = i; j < n; ++j)
if (fabs(a[r][i]) < fabs(a[j][i]))
r = j;
if (r != i)
swap_ranges(a[r].begin(), a[r].begin() + n + 1, a[i]);
for (int j = n; j >= i; --j)
for (int k = i + 1; k < n; ++k)
a[k][j] -= a[k][i] * a[i][j] / a[i][i];
}
for (int i = n - 1; ~i; --i)
{
for (int j = i + 1; j < n; ++j)
a[i][n] -= a[j][n] * a[i][j];
a[i][n] /= a[i][i];
}
}
|
线性基
向量线性基
add 返回要插入的向量 z 是否与已插入的线性无关。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| struct Base
{
vector<vector<double>> v;
Base(int N) : v(N, vector<double>(N, 0)) {} //R^N的子空间
bool add(vector<double> x)
{
for (int i = 0; i < x.size(); ++i)
if (fabs(x[i]) > EPS)
{
if (fabs(v[i][i]) < EPS)
return v[i] = x, 1;
double t = x[i] / v[i][i];
for (int j = 0; j < x.size(); ++j)
x[j] -= t * v[i][j];
}
return 0;
}
};
|
异或线性基
若要查询第 k 小子集异或和，则把 k 写成二进制，对于是 1 的第 i 位，把从低位到高位第 i 个不为 0 的数异或进答案。若要判断是否有非空子集的异或和为 0，如果不存在自由基，那么说明只有空集的异或值为 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
| struct BaseXOR
{
vector<ll> a;
BaseXOR() : a(64, 0) {}
ll ask() //查询最大子集异或和
{
ll t = 0;
for (int i = a.size() - 1; ~i; --i)
t = max(t, t ^ a[i]);
return t;
}
bool add(ll x)
{
for (int i = a.size() - 1; ~i; --i)
if (x >> i & 1)
{
if (a[i])
x ^= a[i];
else
return a[i] = x, 1;
}
return 0;
}
bool check(ll x) //判断一个数是否能够被异或出，0根据需要特判
{
for (int i = a.size() - 1; ~i; --i)
if (x >> i & 1)
if (x ^= a[i], !x)
return 1;
return 0;
}
};
|