交点个数为偶数，一个经典的 Trick 是计算总方案数和与 $\sum\limits_{匹配} (-1)^{匹配交点个数}$，答案就是二者相加后除以 $2$。

总匹配个数是好算的，考虑计算后者。

考虑选出被匹配的点，对完美匹配计数，不难发现 $2k$ 个相同颜色点的完美匹配个数一定是 $1$。

证明考虑归纳，枚举 $2k$ 匹配的点 $p$，$f_{2k}=\sum\limits_{p=1}^{2k-1} (-1)^{2k-p-1}f_{2k-2}=f_{2k-2}$，又因为 $f_2=1$，故 $f_{2k}=1$。

因此只需要考虑不同颜色的交点，假设序列中只有颜色 $1$，然后每次往序列中插入一对匹配的 $2$，容易发现形成交点的奇偶性等于两个 $2$ 中间相差 $1$ 的距离，而两个 $1$ 之间的距离与【序列的逆序对增加量】奇偶性相同。

因此答案就是序列逆序对模 $2$ 的值。

进行图论建模，连接满足 $ia_j$ 的 $(i,j)$，交点个数就是我们选出的导出子图边数。

原问题转化为，选出 $G(V,E)$ 的导出子图，要求每个颜色都选择了偶数次，求 $\sum\limits_{V'\in V} (-1)^{e(V')}$。

先考虑不要求每个点选择偶数次怎么做。

这是一个经典的线性代数问题，设邻接矩阵为 $G$，答案是：

$$ \sum\limits_{\{x_1,x_2,\dots x_n\}\in \{0,1\}^{n}}(-1)^{\left ( \sum G_{u,v}x_u x_v \right) } $$

考虑仿照消元，强行分离出一个点的贡献，但是这里答案式子有交叉项，因此考虑每次消除两个点。

选出点 $u,v$，满足 $u,v$ 有边，将答案式子变为： $$ \sum (-1)^{q(\text{rest})+\text{contrib}(u,v)} $$ 其中 $q(\text{rest})$ 表示原问题去掉 $u,v$ 的子问题，$\text{contrib}(u,v)$ 表示 $u,v$ 之间和 $u,v$ 与其余点的贡献。

定义： $$ \alpha=G_{u,u} \\ \beta=G_{v,v} \\ f=\sum_{i\in \text{adj}(u),i\neq v} x_i \\ g=\sum_{i\in \text{adj}(v),i\neq u} x_i $$ 那么有： $$ \text{contrib}(u,v)=\sum_{x_u,x_v} (-1)^{x_ux_v+x_u(\alpha+f)+x_v(\beta+g)} \\ =2\cdot (-1)^{\alpha\beta+\alpha g+\beta f+fg} $$ 因此，我们删去 $u,v$ 后，需要对 $G$ 进行的操作是：

• 答案乘 $2$。
• $\alpha\beta$：如果 $u,v$ 都有自环，答案乘 $-1$。
• $\alpha g$：如果 $u$ 有自环，$g$ 中每个点的贡献都要乘以 $-1$，那么给 $g$ 中的每个点加上一个自环即可。
• $\beta f$：与 $\alpha g$ 对称。
• $fg$：记 $S_f=\{i|i\in \text{adj}(u),i\neq v\},S_g=\{j|j\in \text{adj}(v),j\neq u\}$，这部分的贡献拆开后是 $\sum_{i\in S_f}\sum_{j\in S_g} x_i x_j$，对应的操作是翻转 $S_f,S_g$ 的所有连边。

重复次过程直到剩下若干孤点和若干孤自环，如果有孤自环则答案为 $0$，否则答案为 $2^{孤点个数}$。

最后答案是 $2$ 的若干次幂。现在考虑加上【每个颜色选偶数个点】的限制，不难发现可以给每个颜色 $c$ 新加一个点 $X_c$，$X_c$ 与所有颜色为 $c$ 的点都有边，由于 $deg(X_c)$ 必为偶数，因此如果选择奇数个点，那么选/不选虚点的清空可以抵消，因此可以自动计算出颜色 $c$ 选出偶数个点的答案。最后答案需要除以 $2^{虚点个数}$。

使用 bitset 优化在邻接矩阵上的操作，复杂度 $O(\frac{n^3}{w})$。