SoyTony 的博客

SoyTony 的博客

¡Bienvenidos!

ABC321G

posted on 2023-09-24 08:06:31 | under 题解 |

一个经典的连通容斥。

看到数据范围容易想到一个 $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