自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 23:00:14，当前版本为作者最后更新于2024-07-06 21:58:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑每条边有一个权值 $a_i$，那么 $a_i$ 之间需要满足若干个方程：对于两条不同的 $u\to v$ 的路径，两条路径上的 $a_i$ 异或和需要 $=0$。

那么就是要求解满足若干个方程的 $a_i$ 的解数。把这些方程插入线性基里，若得到的线性基的大小（秩）为 $k$，则答案为 $2^{m-k}$。

以每个点 $u$ 为根，向外 dfs 得到一棵外向树。对于一条非树边 $x\to y$，就有两条路径 $(u\to x)\to y$ 和 $(u\to y)$。把这两条路径异或起来，得到的方程插入线性基。

对于使用 $\ge 2$ 条非树边的情况，不难发现已经被原有的方程表示了。

这样能得到 $nm$ 条方程，总共 $nm$ 次线性基插入，复杂度为 $O(nm\times \frac{m^2}{w})$，在 $n,m\le 400$ 时可以通过。

https://qoj.ac/submission/423354