一点线性代数

学完就忘，重学。不过说实话，对于校内上的那种[“线性代数”]^(100以内四则运算)忘不忘有意义吗。

和标题一样，就只有一点，而且组织混乱。

略过部分

  • 线性相关
  • Span
  • …

下面所有的内容都是基于向量空间内的意义。

行列式

行列式评价了一个线性变换对空间的放缩程度。对于一个二维空间，它就评价了对有向面积的放缩比例，三维则是体积。

所以对于行列式为0的变换，依照其意义，可以认为将空间进行了“降维”（压扁，但是它仍然在那个维度上）。那么这也是能够使用行列式判断一个向量组是否满秩（张成的空间和向量维数一致）的直观表现。

这同时也是可以使用行列式计算三维空间下的体积的直观表现，如果你把平行六面体理解成是单位立方体的变换。

∣M1M2∣=∣M1∣∣M2∣|M_1M_2|=|M_1||M_2|

基

基是向量空间中的概念，指的是一个可以张成向量空间VV的线性无关向量组B\mathfrak {B}。而对于一般情况下的有限向量空间，求解其基的方法就是从向量空间内依次删除线性相关项，直到其变为线性无关组。

其满足以下性质

  • VV是B\mathfrak {B}的极小生成集，B\mathfrak {B}的任何子集都无法张成VV。
  • B\mathfrak {B}是VV的极大线性无关组。

线性基

当计算为异或时，可以将整数以二进制分解作为向量，在这种意义下对这样的一个整数集合求基称为线性基。

其求法就像上文所说的求法，依次的考虑某一个整数是否限性相关。在实际编写时通过高斯消元来完成。

其具体思路为维护一个对角矩阵。由高位开始使用已有元素对新加入的元素进行消元，若完全消除，则线性相关；若未完全消除（由高位计算到第i位时无法消除），则将其计入基中，并使用所有剩余的低位对该元素对应位置继续消元，再使用该元素向上对先前的所有元素第i位进行消元。如此的复杂度O(nlg⁡n)O(n\lg n)。

由这个过程，我们能够得到的信息包含但不限于

  1. 基：一组由原整数组组成的基，由消元过程判断。
  2. 线性基：一组由原整数张成空间中的标准基。

一向量空间的所有基的长度相同，同时称为空间的维数。对于一个由n维的向量构成的向量空间，其维数不大于n。

Problem: Exclusive OR

Given nn integers A1,⋯ ,AnA_1,\cdots , A_n. For all 1≤i≤n1\leq i \leq n, determine the maximum value by caculating xor of ii numbers that are repeatly chosen from AA.

1≤n≤2×105,0≤Ai<2181\leq n \leq 2 \times 10^5, 0 \leq A_i < 2^{18}

利用异或卷积，令a[i]表示数i是否出现过，那么

bk=∑i∑jaiaj[i xor j=k]b_k=\sum_i\sum_j a_ia_j[i~\text{xor}~j =k]

即异或和为kk的方案数。把aa自己卷自己，统计每次卷完有方案的最大的kk。

对于集合A，其张成的空间维数不可能超过18，则至多选择18个向量就可以构成其基，至多有18个向量就可以取到最大的xor。而从构成最大的向量开始，接下来就只是选择一个元素加入（所以至少算到19）和抵消，即每隔1个答案相同了。

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
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <tuple>
using namespace std;
using ll = long long;
const int XN = 650000;
const int MOD = 998244353;
ll INV2 = 0;

ll qpow(ll x, ll a) {
    ll res = 1;
    for (; a; a >>= 1, x = (ll)x * x % MOD) {
        if (a & 1)res = (ll)res * x % MOD;
    }
    return res % MOD;
}

template<class T>
void FWT(ll a[], int n, T F) {
    for (int len = 2; len <= n; len *= 2)
        for (int i = 0; i < n; i += len)
            for (int j = i; j < i + len / 2; ++j)
                F(a[j], a[j + len / 2]);
}

void Txor(ll& x, ll& y) {
    auto a = (x + y) % MOD;
    auto b = (x - y + MOD) % MOD;
    x = a, y = b;
}

void Ixor(ll& x, ll& y) {
    auto a = (x + y) * INV2 % MOD;
    auto b = (x - y) * INV2 % MOD;
    x = a, y = b;
}
int ans[XN];
ll a[XN], b[XN];
int main() {
    ios::sync_with_stdio(false);
    INV2 = qpow(2, MOD - 2);

    int n;
    cin >> n;
    int maxx = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        maxx = max(x, maxx);
        a[x] = 1;
        b[x] = 1;
    }
    int t = 1;
    while (t <= maxx)t *= 2;

    ans[1] = maxx;
    FWT(b, t, Txor);
    for (int i = 2; i <= 20; i++) {
        FWT(a, t, Txor);
        for (int i = 0; i <= t; i++) {
            a[i] = (ll)a[i] * b[i] % MOD;
        }
        FWT(a, t, Ixor);
        for (int j = t; j >= 0; j--) {
            if (a[j]) {
                ans[i] = j;
                break;
            }
        }
    }
    for (int i = 21; i <= n; i++)ans[i] = ans[i - 2];
    for (int i = 1; i <= n; i++)cout << ans[i] << " ";
    cout << endl;

    return 0;
}

线性变换

这里主要考虑通过矩阵对向量空间进行线性变换。考虑的办法主要是基于对基的操作。通过将某一个变换拆解为单一动作的矩阵，我们能够方便的去玩空间。

例如，计算三维空间中的某个点P按一条线AA为轴旋转γ\gamma度后的位置。一个粗暴的思路是先将xx轴转到AA上去，计算PP于原位置在新的基下的坐标P′P'，对P′P'以xx轴旋转θ\theta度，对此时的P′P'重新逆回原基下的坐标。

以三维直线在x−yx-y平面上的投影和xx轴正半轴的夹角为θ\theta，以直线与zz轴正半轴的夹角为ϕ\phi，那么首先以θ\theta旋转，再以ϕ\phi旋转即可把xx轴转到AA上去。两次旋转的变换矩阵分别为

以z轴旋转。

Mz=[cos⁡θ−sin⁡θ0sin⁡θcos⁡θ0001]M_z=\begin{bmatrix} \cos \theta & -\sin \theta & 0 \cr \sin \theta & \cos \theta & 0 \cr 0 & 0 & 1 \end{bmatrix}

以y轴旋转

My=[sin⁡ϕ0−cos⁡ϕ010cos⁡ϕ0sin⁡ϕ]M_y=\begin{bmatrix} \sin \phi & 0 & -\cos \phi \cr 0 & 1 & 0 \cr \cos \phi & 0 & \sin \phi \end{bmatrix}

在此时，对于由Ω\Omega以MM变换到的Ω′\Omega'，在Ω′\Omega'空间下的坐标左乘变换MM就能得到其在Ω\Omega的坐标。MM即为Ω′\Omega'和Ω\Omega之间的桥梁。

那么，考虑如何将二者复合。首先执行z轴旋转，将xx转到AA在x−yx-y平面上的投影位置，得到空间Ω′\Omega'。而后，我们需要对在Ω\Omega下Ω′\Omega'的基在Ω′\Omega'下的坐标再次执行yy轴旋转将其最终转到AA上去，称为空间Ω1\Omega_1，再把Ω′\Omega'下的Ω1\Omega_1的基换算回Ω\Omega里，准备进行下一步的转换。这个过程即

MzMy(Mz−1MzI)=MzMyM_zM_y(M_z^{-1}M_zI)=M_zM_y

然后计算PP位于Ω1\Omega_1下的坐标，即求解MP′=P  ⟹  P′=M−1PMP'=P \implies P'=M^{-1}P，计算∣M∣|M|恒非00，则P′P'总可求出。而后对P′P'执行以xx轴（即A）旋转题目给定的γ\gamma角。再次计算MP′MP'求出PP即为答案。

以xx轴旋转

Mx=[1000cos⁡γsin⁡γ0−sin⁡γcos⁡γ]M_x=\begin{bmatrix} 1 & 0 & 0 \cr 0 & \cos \gamma & \sin \gamma \cr 0 & -\sin \gamma & \cos \gamma \end{bmatrix}

这几个矩阵简单画一下图就可以推出来。逆矩阵使用高斯消元处理伴随矩阵即可。