ABC321G

一个经典的连通容斥。 看到数据范围容易想到一个 $O(3^n)$ 的枚举子集，问题现在变成求一个中间点集合 $S$ 连通的方案数，设为 $h_S$，首先 $S$ 的红蓝点个数应当相等，记作 $sum_S$，容斥枚举 $\mathrm{lowbit}(S)=x$ 所在集合 $T$，形如： $$h_S=sum_S!-\sum_{T\subsetneq S,x\in T} h_T\times sum_{S\setminus T}!$$ 之后就是把连通块拼起来，设 $f_S$ 为连通块个数总和，$g_S$ 为总方案数，这里防止算重也要加入 $\mathrm{lowbit}(S)=x$ 所在集合 $T$，形如： $$f_S\leftarrow f_{S\setminus T}\times h_T+g_{S\setminus T}\times h_T$$ $$g_S\leftarrow g_{S\setminus T}\times h_T$$ 答案就是 $\frac{1}{m!}f_S$。 提交记录：[Submission - AtCoder](https://atcoder.jp/contests/abc321/submissions/45871383)