主要思路
我操，这么暴力？
首先对于每一个子图而言，我们需要得到其合法性和对答案的贡献。做完之后，用子集卷积就行了。
Continue reading →其实就是做 \((1 + 2x^{a_i})\) 的异或卷积得组成 \(0\) 的方案。一种想法是做多次 FWT，但是这样铁定超时。我们考虑观察一下性质。
其实考虑 FWT 的变换就是：
\[ b_i = \sum_{j} (-1)^{cnt(i \& j)} a_j \]
Continue reading →这题还挺好的。最后异或出来的路径是有链和环组成的。我们可以把链和环分开来求，因为从链上某点到环上某点之间的距离可以计算两次，所以不造成影响。所以我们可以把链做一个多项式，环做一个多项式，在做一遍 FWT_XOR 就完美了。
记公式：
Or operation:
arr[k + step] += opt * arr[k]
And operation:
arr[k] += opt * arr[k + step]
Xor operation:
A = arr[k], B = arr[k + step]
arr[k] = A + B, arr[k + step] = A - B
with inverse-operation, the inv2 is needed:
arr[k] /= 2, arr[k + step] /= 2;