[洛谷P5169]xtq的异或和

题目大意：给你一张$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;

}

巴特西

[洛谷P5169]xtq的异或和

最新文章

热门文章