反演，乃反向推演。放缩限制，得关系式，使斯特林反演，得解。
求选出的异或图为连通图得方案数，连通不好刻画，我会小学生容斥：设 \(f_{\pi}\) 为连通情况为 \(\pi\) 的选法数量（\(\pi\) 代表一种划分，划分出的同一块内点连通，不同块间没有连边），此时考虑经典放缩限制：设 \(g_{\pi}\) 表示 \(\pi\) 划分下的块间没有连边但是对块内连发没有要求的方案数。\(f,g\) 之间是可以有第二类斯特林数的反演关系在的，因为 \(f\) 可以看作对 \(g\) 的划分的进一步细化，也就是子集划分嘛。
但是感觉对每种划分 \(\pi\) 来考虑很难做，所以考虑转化一下，只记录块数。那么容易有 \(g_m=\sum\limits_{k=m}^n \begin{Bmatrix}k \\ m\end{Bmatrix} f_k\)，很好理解，就是把 \(k\) 个连通块划分到 \(m\) 个块里面。反演回去就有 \(f_m=\sum\limits_{k=m}^n (-1)^{k-m}\begin{bmatrix}k \\ m\end{bmatrix} g_k\)，由于最终要求连通，所以只求 \(f_1=\sum\limits_{k=1}^n (-1)^{k-1}(k-1)! g_k\)。
问题在于求 \(g_k\)。假设枚举了一种划分，那么就相当于这样一个问题：每个集合有一些元素，钦定一些元素最后系数为零，求有多少种选集合的方式使所选集合的异或和满足条件。只保留这些集合中被限制了的那些元素位，那么就变成了选出若干个集合使其异或和为 \(0\) 的方案数。简单线性基问题，假如所有集合代表的二进数构造出的线性基中有 \(x\) 个元素，总共有 \(s\) 个可选集合，那么就有 \(2^{s-x}\) 种选法，因为 \(x-s\) 就是这个异或方程组中的自由元个数，\(x\) 就是主元个数。
有一个枚举划分的小技巧，就是将划分看作染色，同时要求点 \(i\) 染的颜色要么是 \(1\sim i-1\) 中出现过的，要么是新的一种颜色，但是颜色编号连续，这样可以保证颜色序列的“连续性”，从而不重不漏。划分数（贝尔数）的大小是这样的，算一下总运算量 \(10^9\) 左右，使用普通的非高斯消元线性基才能过，高消了的线性基因为插入常数较大会被卡常/fn
标签：果然,连通,异或,反演,划分,集合,常数,pi From： https://www.cnblogs.com/Tsukinaga-Ichiyo/p/18238621