关于 k 进制线性基

本质还是高斯消元，使其成为上三角矩阵。但是 \(k\) 不一定是质数。

但我们不需要保证已有数字不改变，只要维护的是一个上三角矩阵就行。所以我们可以利用更相减损让其中一个向量的最高位 \(= 0\) 。然后插入即可。正确性的证明同二进制线性基。

然后来到了查询环节。在二进制下，异或两次就等于没异或，所以容易判断。但是在这里，一个数的异或次数是不固定的。更糟的是，很有可能有多种方式取得最大值。

举个例子。当前 \(k = 8\) ，最高位 \(= 6\) ，初始数字 \(x = 0\) 。显然异或一次得到 \(6\) 是最好的。但是，异或五次同样可以得到 \(6\) ，而且对后面有影响！

这里就要用一个类似完全背包的操作了。因为，我们确信，如果最高位是 \(v(v\ne 0)\)，那么异或这个数 \(\frac{k}{\gcd(k,v)}\) 次，在当前位的异或值不会变。

那么，只要在线性基里额外插入一个当前位置的数的 \(\frac{k}{\gcd(k,v)}\) 次异或值，就会自动完成对后面位置的修正。

最后算一下时间复杂度：

首先计算插入，不妨设 \(k\le x\)，否则整个算法是 \(\mathcal O(q+\log x)\) 的。辗转相除最多 \(\mathcal O(\log_2 k)\) 次，每次要 \(\mathcal O(\log_kx)\) 把一整行的信息全部修改，并且每个数字必然从头到尾访问所有 \(\mathcal O(\log_k x)\) 个元素（因为有了上面的 “修正法案”，插入成功也会继续往下尝试插入），复杂度 \(\mathcal O(\log_2 x\cdot \log_k x)\) 。

然后计算查询，仍然设 \(k\le x\)，否则整个算法是 \(\mathcal O(q\log x)\) 的。对于每一位，我们要计算当前位可以得到的最小值，这需要 \(\mathcal O(\log_k x)\) 的行向量操作。一共 \(\mathcal O(\log_k x)\) 行，总复杂度 \(\mathcal O(\log_k^2x)\) 。

「IOI2021国家队选拔」术数树

点击查看代码

#include <bits/stdc++.h>

using namespace std;

int q, k, m;

struct Vector {

    int a[31];

    Vector(int _x = 0) {

        memset(a, 0, sizeof(a));

        for (int i = 0; _x; i++) {

            a[i] = _x % k;

            _x /= k;

        }

    }

    inline int &operator[](int t) { return a[t]; }

    inline Vector operator+(Vector b) {

        Vector res;

        for (int i = 0; i < m; i++) res[i] = (a[i] + b[i]) % k;

        return res;

    }

    inline Vector operator-(Vector b) {

        Vector res;

        for (int i = 0; i < m; i++) res[i] = (a[i] - b[i] + k) % k;

        return res;

    }

    inline Vector operator*(int b) {

        Vector res;

        for (int i = 0; i < m; i++) res[i] = 1ll * b * a[i] % k;

        return res;

    }

} bas[31], dis[200005];

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }

void exgcd(int a, int b, int &x, int &y) {

    if (!b) {

        x = 1;

        y = 0;

        return;

    }

    exgcd(b, a % b, y, x);

    y -= a / b * x;

}

inline int Inv(int x) {

    int a, b;

    exgcd(x, k, a, b);

    return (a + k) % k;

}

inline void insert(Vector x) {

    for (int i = m - 1; ~i; i--) {

        if (!x[i])

            continue;

        if (!bas[i][i]) {

            bas[i] = x * Inv(x[i]);

            x = x * (k / gcd(k, x[i]));

        }

        while (x[i]) {

            int t = bas[i][i] / x[i];

            bas[i] = bas[i] - x * t;

            swap(x, bas[i]);

        }

    }

}

inline Vector query(Vector x) {

    for (int i = m - 1; ~i; i--) {

        if (!bas[i][i])

            continue;

        x = x - bas[i] * (x[i] / bas[i][i]);

    }

    return x;

}

int fa[19][200005], dep[200005];

inline int lca(int x, int y) {

    if (dep[x] < dep[y])

        swap(x, y);

    for (int i = 18; ~i; i--)

        if (dep[fa[i][x]] >= dep[y])

            x = fa[i][x];

    if (x == y)

        return x;

    for (int i = 18; ~i; i--) {

        if (fa[i][x] != fa[i][y])

            x = fa[i][x], y = fa[i][y];

    }

    return fa[0][x];

}

int tot = 1;

inline Vector dist(int x, int y) {

    int lc = lca(x, y);

    return dis[x] + dis[y] - dis[lc] * 2;

}

int main() {

    freopen("city.in", "r", stdin);

    freopen("city.out", "w", stdout);

    scanf("%d%d%d", &q, &k, &m);

    for (int i = 0; i < 19; i++) fa[i][1] = 1;

    while (q--) {

        int op, x, y, v;

        scanf("%d", &op);

        if (op == 1) {

            scanf("%d%d", &x, &v);

            insert(Vector(v) + Vector(v));

            dis[++tot] = dis[x] + Vector(v);

            dep[tot] = dep[x] + 1;

            fa[0][tot] = x;

            for (int i = 1; i < 19; i++) fa[i][tot] = fa[i - 1][fa[i - 1][tot]];

        } else if (op == 2) {

            int x, y, v;

            scanf("%d%d%d", &x, &y, &v);

            insert(dist(x, y) + Vector(v));

        } else {

            scanf("%d%d", &x, &y);

            Vector tmp = query(dist(x, y));

            long long res = 0;

            for (int i = m - 1; ~i; i--) res = k * res + tmp[i];

            printf("%lld\n", res);

        }

    }

    return 0;

}

巴特西

关于 k 进制线性基

「IOI2021国家队选拔」术数树

最新文章

热门文章