题解 P5169 【xtq的异或和】

Memory_of_winter · 2019-01-14 19:48:40 · 题解

我的博客

题目大意：给你一张n(n\leqslant10^5)个点m(m\leqslant3\times10^5)条边的无向图，每条边有一个权值，q(q\leqslant2^{18})次询问，每次询问给你一个x(x<2^{18})，问有多少个有序点对(u,v)，满足有一条u到v的路径异或和为x

题解：先建一棵生成树，把图中所有环丢进线性基，发现一条u->v的路径就是树上u->v的距离异或上一些环。

发现x<2^{18}，所以可以把线性基中所有可以表示出来的数求出来为集合S，令多项式A(x)，满足[x^n]A(x)=\sum\limits_{i=1}^n[dis_i=n]；令多项式B(x)，满足[x^n]B(x)=[n\in S]，dis_i表示第i个点到根的路径异或值

然后答案就是A*A*B，*表示异或卷积

C++ Code：

#include <cstdio>
#include <iostream>
#define maxn 100010
#define maxm 300010
#define N 262144
const int mod = 998244353;

int head[maxn], cnt;
struct Edge {
    int to, nxt, w;
} e[maxm << 1];
inline void addedge(int a, int b, int c) {
    e[++cnt] = (Edge) { b, head[a], c }; head[a] = cnt;
    e[++cnt] = (Edge) { a, head[b], c }; head[b] = cnt;
}

long long A[N], B[N];
namespace Base {
#define M 18
    int p[M + 1];
    inline void insert(int x) {
        for (int i = M; ~i; --i) if (x >> i & 1) {
            if (p[i]) x ^= p[i];
            else { p[i] = x; break; }
        }
    }
    void dfs(int dep, int val) {
        if (dep > M) {
            ++B[val];
            return ;
        }
        dfs(dep + 1, val);
        if (p[dep]) dfs(dep + 1, val ^ p[dep]);
    }
#undef M
}

int n, m, q;
int dis[maxn];
bool vis[maxn];
void dfs(int u, int fa = 0) {
    vis[u] = true;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!vis[v]) {
            dis[v] = dis[u] ^ e[i].w;
            dfs(v, u);
        } else Base::insert(dis[u] ^ dis[v] ^ e[i].w);
    }
}

const int lim = N;
inline void FWT(long long *A) {
    for (register int mid = 1; mid < lim; mid <<= 1)
        for (register int i = 0; i < lim; i += mid << 1)
            for (register int j = 0; j < mid; ++j) {
                const long long X = A[i + j], Y = A[i + j + mid];
                A[i + j] = X + Y, A[i + j + mid] = X - Y;
            }
}

int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    std::cin >> n >> m >> q;
    for (int i = 0, a, b, c; i < m; ++i) {
        std::cin >> a >> b >> c;
        addedge(a, b, c);
    }
    dfs(1), Base::dfs(0, 0);
    for (int i = 1; i <= n; ++i) ++A[dis[i]];
    FWT(A), FWT(B);
    for (int i = 0; i < lim; ++i) A[i] = A[i] * A[i] * B[i];
    FWT(A);
    for (int i = 0; i < lim; ++i) A[i] >>= 18;
    while (q --> 0) {
        static int x;
        std::cin >> x;
        std::cout << A[x] % mod << '\n';
    }
    return 0;
}