uoj192 【UR #14】最强跳蚤

曾经终败给现在 2023-10-11 05:14 9阅读 0赞

[题目][Link 1]

和成爷达成一致，被卡随机的话就是过了

考虑一个完全平方数的所有质因子次幂一定是偶数，于是对于每一条边我们都只保留其出现次数为奇数的质因子

注意到有一个点的\\(w\\leq 80\\)，于是考虑状压质因子，对于第\\(i\\)个质数，我们定义其权值为\\(2^\{i-1\}\\)，这样我们就把每一条边的权值都变成了一个二进制数，现在只需要求有多少条路径的异或和为\\(0\\)即可，显然求一下每个点到根路径异或和，开个桶随便搞搞就完事了

对于\\(w\\leq 10^8\\)，我们不能再状压成二进制了，考虑对每个质因子设置一个\\(\\rm unsigned\\ long \\ long\\)范围内的权值，一条边的权值就是所有出现次数为奇数的质因子权值的异或和，还是求有多少条路径异或为\\(0\\)

之后就被卡了，各种换随机种子也只有90

代码

#include <bits/stdc++.h>
    #define re register
    #define LL long long
    #define max(a, b) ((a) > (b) ? (a) : (b))
    #define ull unsigned long long
    inline int read() {
        char c = getchar();
        int x = 0;
        while (c < '0' || c > '9') c = getchar();
        while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - 48, c = getchar();
        return x;
    }
    const int maxn = 1e5 + 5;
    struct E {
        int v, nxt;
        ull w;
    } e[maxn << 1];
    int n, num, T, f[10005], p[10005];
    int head[maxn], xx[maxn], yy[maxn], ww[maxn];
    ull w[10005], pre[maxn];
    std::map<int, ull> ma;
    std::map<ull, int> tax;
    inline void add(int x, int y, ull w) {
        e[++num].v = y;
        e[num].nxt = head[x];
        head[x] = num;
        e[num].w = w;
    }
    inline ull Rand() {
        return (((ull)rand() % 32768ll) << 45ll) + (((ull)rand() % 32768ll) << 30ll) +
               (((ull)rand() % 32768ll) << 15ll) + ((ull)rand() % 32768ll);
    }
    void dfs(int x, int fa) {
        for (re int i = head[x]; i; i = e[i].nxt) {
            if (e[i].v == fa)
                continue;
            pre[e[i].v] = pre[x] ^ e[i].w;
            dfs(e[i].v, x);
        }
    }
    int main() {
        srand(19260817);
        n = read();
        for (re int i = 1; i < n; i++) xx[i] = read(), yy[i] = read(), ww[i] = read(), T = max(T, ww[i]);
        T = std::ceil(std::sqrt(T));
        for (re int i = 2; i <= T; i++) {
            if (!f[i])
                p[++p[0]] = i, w[p[0]] = Rand();
            for (re int j = 1; j <= p[0] && p[j] * i <= T; ++j) {
                f[p[j] * i] = 1;
                if (i % p[j] == 0)
                    break;
            }
        }
        for (re int i = 1; i < n; i++) {
            int now = 0;
            for (re int t = 0, j = 1; j <= p[0]; ++j, t = 0) {
                if (ww[i] % p[j])
                    continue;
                while (ww[i] % p[j] == 0) ww[i] /= p[j], t ^= 1;
                now ^= (t * w[j]);
                if (ww[i] == 1)
                    break;
            }
            if (ww[i] != 1) {
                if (!ma[ww[i]])
                    ma[ww[i]] = Rand();
                now ^= ma[ww[i]];
            }
            add(xx[i], yy[i], now), add(yy[i], xx[i], now);
        }
        dfs(1, 0);
        LL ans = 0;
        for (re int i = 1; i <= n; i++) ans += tax[pre[i]], tax[pre[i]]++;
        printf("%lld\n", 2ll * ans);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11469426.html

[Link 1]: http://uoj.ac/problem/192