自动搬运

查看原文

来自洛谷，原作者为

	Memory_of_winter ことりのおやつにしてやるぞー！

搬运于2025-08-24 22:07:51，当前版本为作者最后更新于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;
}