P10682 Tikvani

Rainbow_qwq · 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