k 进制异或线性基

不知道 nfls 模拟赛为什么出这种抽象东西，也不知道这玩意有什么用。

定义 $k$ 进制异或为 $k$ 进制下的不进位加法。

至于为什么可以对 $k$ 进制异或这种运算构建线性基，由于我不懂抽象代数相关知识，就没法在此处展开了，以下内容主要适合感性理解。

算法的大致框架和二进制异或线性基是一致的，我们仍贪心的让每个数去「控制」尽可能高的位。考虑二进制异或线性基中的每个步骤在推广后需要做哪些改变。

我们用序列 $a$ 表示线性基中的数，其中 $a_i$ 控制第 $i$ 个 $k$ 进制位。我们用 $x^{(i)}$ 表示 $x$ 的第 $i$ 个 $k$ 进制位。下文中涉及到的加减法均为 $k$ 进制不进位加减法，乘法 $a\times b$ 则表示将 $a$ 个 $b$ 用 $k$ 进制不进位加法合并。

考虑我们现在要向线性基中插入一个数 $x$。从高到低枚举每一位，假设现在枚举到了第 $i$ 位，且 $x^{(i)}\ne 0$。

若 $a_i$ 有值，在二进制异或线性基中，我们会将 $x$ 的第 $i$ 位异或成 $0$，然后继续考虑低位。$k$ 进制异或线性基中的问题在于，$(ta_i)^{(i)}$ 只能取到所有 $\gcd(a_i^{(i)},k)$ 的倍数，在 $\gcd\ne 0$ 时，$x$ 对第 $i$ 位不一定没有贡献。此处我们对 $x$ 和 $a_i$ 做辗转相减，直到 $x^{(i)}=0$，此时 $a_i^{(i)}$ 会变为 $\gcd(a_i^{(i)},x^{(i)})$。

若 $a_i$ 没有值，我们直接令 $a_i\gets x$。但插入过程不能在此处终止，原因在上文中提到过，$(ta_i)^{(i)}$ 只能取到所有 $\gcd(a_i^{(i)},k)$ 的倍数，故可能存在多个 $t\in[0,k)\cup \mathbb Z$ 能使 $(ta_i)^{(i)}$ 取到某特定值，但此时两数的低位不同，在查询时，我们便不能确定要使用那个系数。注意到使 $(ta_i)^{(i)}$ 相等的 $t$ 之间总是间隔 $k/\gcd(a_i^{(i)},k)$ 或其倍数，所以我们将 $x'=\left(k/\gcd(a_i^{(i)},k)\right)\cdot x$ 再次插入线性基即可，$x'^{(i)}=0$，在实现时只需令 $x\gets x'$ 然后继续向低位循环即可。

接下来考虑查询 $x$ 异或上线性基内数能得到的最小值。仍然从高到低考虑每一位，假设现在枚举到了第 $i$ 位，且 $x^{(i)}\ne 0,a_i^{(i)}\ne 0$。

我们不一定能将 $x^{(i)}$ 调整至 $0$，再次提到 $(ta_i)^{(i)}$ 只能取到所有 $\gcd(a_i^{(i)},k)$ 的倍数，所以 $x^{(i)}$ 能异或出的最小值为 $x^{(i)}\bmod \gcd(a_i^{(i)},k)$，这里可以通过 exgcd 求出取到最小值时 $a_i$ 前的系数。我的实现方式则是，在插入时就做 exgcd，将 $a_i^{(i)}$ 调整至 $\gcd(a_i^{(i)},k)$，这样在查询时就可以直接算了。

单次插入和单次查询的复杂度均为 $O(\log^2V)$。

参考实现：

struct base_k{
    static const int L = 26;
    int a[L];
    base_k() = default;
    base_k(int x) { for(int i = 0; i < L; i++) a[i] = x % k, x /= k; }
    int to_int(){
        int res = 0;
        for(int i = L - 1; i >= 0; i--) res = res * k + a[i];
        return res;
    }
    int& operator[](const int &index) { return a[index]; }
    const int& operator[](const int &index) const { return a[index]; }
    base_k operator+(const base_k &b) const {
        base_k res;
        for(int i = 0; i < L; i++) res[i] = (a[i] + b[i]) % k;
        return res;
    }
    base_k operator-(const base_k &b) const {
        base_k res;
        for(int i = 0; i < L; i++) res[i] = (a[i] - b[i] + k) % k;
        return res;
    }
    base_k operator*(const int &x) const {
        base_k res;
        for(int i = 0; i < L; i++) res[i] = (a[i] * x % k + k) % k;
        return res;
    }
};
int exgcd(int a, int b, int &x, int &y){
    if(b == 0) { x = 1, y = 0; return a; }
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
struct linear_basis{
    static const int L = 26;
    base_k a[L];
    void insert(base_k x){
        for(int i = L - 1; i >= 0; i--){
            if(x[i] == 0) continue;
            if(a[i][i] == 0){
                a[i] = x;
                int p, q; 
                int g = exgcd(a[i][i], k, p, q);
                a[i] = a[i] * p;
                x = x * (k / g);
            }
            else{
                while(x[i]){
                    if(x[i] < a[i][i]) swap(x, a[i]);
                    x = x - a[i] * (x[i] / a[i][i]);
                }
            }
        }
    }
    base_k query_min(base_k x){
        for(int i = L - 1; i >= 0; i--){
            if(a[i][i]){
                x = x - a[i] * (x[i] / a[i][i]);
            }
        }
        return x;
    }
};

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。