uoj192 【UR #14】最强跳蚤

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

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

注意到有一个点的\(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;

}

巴特西

uoj192 【UR #14】最强跳蚤

最新文章

热门文章