n\le 15

状压图计数

DAG 子图计数

$$\begin{aligned} f_S&=\sum_{\emp\ne T\sube R\sube S}(-1)^{|R|-|T|}2^{\w(R,S\sm R)}f_{S\sm R}\\ &=\sum_{\emp\ne R\sube S}(-1)^{|R|}2^{\w(R,S\sm R)}f_{S\sm R}\sum_{\emp\neq T\sube R}(-1)^{|T|}\\ &=\sum_{\emp\ne R\sube S}(-1)^{|R|+1}2^{\w(R,S\sm R)}f_{S\sm R} \end{aligned}$$

强连通子图计数

$$f_S=2^{\w(S,S)}-\sum_{\emp\ne T\sube S}(-1)^{\text{T\;缩点后点数}+1}\,g_T\,2^{\w(T,S\sm T)+\w(S\sm T,S\sm T)}$$ $$\begin{aligned} g_S&=f_S-\sum_{T\sub S,x\in T}f_T g_{S\sm T}\\ f_S&=2^{\w(S,S)}-\sum_{\emp\ne T\sube S}g_T\,2^{\w(T,S\sm T)+\w(S\sm T,S\sm T)} \end{aligned}$$

岁月

• $P$ 强连通：主旋律。
• $U-P$ 没有连向 $P$ 的边：直接计算。
• $P$ 能到达 $U-P$： 设 $f_S(S\supe P)$ 为 $P$ 能到达 $S$ 内的点的概率，$f_P=1$。 $$f_S=1-\sum_{T\sub S,P\sube T}f_T\,2^{-\w(T,S\sm T)}$$

ex

最小生成树的结论，转成对于每种权值，都在把一些连通块合并起来。终点在连通块的根集中的边才有用。

所以 $\gdef\ww{cross'}\ww(S,T)=\w(\{u\mid\exist v\in S,u,v\,\text{在同一连通块中}\},T)$

还是分成三部分：

• 强连通：只需要强制分出来的 $T$ 必须是完整的，即一个连通块不能同时在 $T$ 和 $S\sm T$ 中。
• 没有反边：还是直接算。
• 可达所有点：在这里把每个连通块中的概率算上，同时也要强制 $T$ 完整。

具体可以看代码，需要注意把 dp 倒过来转移时的初始值（即可能的终点）。

重塑时光

$$\begin{aligned} f_{i,S}&=\sum_{j+k=i}\sum_{\emp\ne T\sube S}g_{j,T}f_{k,S\sm T}\noe{T}{S\sm T}\\ g_{i,S}&=\sum_{x\in T\sube S}{\color{red}-}h_Tg_{i-1,S\sm T}\noe{T}{S\sm T}\noe{S\sm T}{T}\\ h_S&=\sum_{x\in S}h_{S\sm \{x\}}\noe{S\sm\{x\}}{\{x\}} \end{aligned}$$

最小边双/点双/强连通生成子图

边双/点双计数

Message Spread

集合幂级数

反演本身是一种容斥，通常把所求的东西的自由度扩大，但是却能将“恰好”、“一一对应”的这一类奇怪的限制给去掉，从而使得在计数角度方面的限制与状态缩小、化简。

容斥原理

$$\left|\bigcap_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m+1}\sum_{T\sube[n],|T|=m}\left|\bigcup_{x\in T}S_x \right|$$ $$\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m+1}\sum_{T\sube[n],|T|=m}\left|\bigcap_{x\in T}S_x \right|$$

子集/超集反演

$$g(S)=\sum_{T\sube S}f(T)$$ $$f(S)=\sum_{T\sube S}(-1)^{|S|-|T|}g(T)$$ $$g(S)=\sum_{T\supe S}f(T)$$ $$f(S)=\sum_{T\supe S}(-1)^{|S|-|T|}g(T)$$

二项式反演

$$g(x)=\sum_{x\le i}\binom{i}{x}f(i)$$ $$f(x)=\sum_{x\le i}(-1)^{x-i}\binom{i}{x}g(i)$$

NOI2025 集合

$$\begin{aligned} Ans&=\sum_{P\sube U}\sum_{Q\sube U}[f(P)=f(Q)][P\cap Q=\emp]val(P)val(Q)\\ &=\sum_{S\sube N}\sum_{P\sube U}[f(P)=S]\sum_{Q\sube U}[f(Q)=S][P\cup Q=\emp]val(P)val(Q)\\ \end{aligned}$$ $$\begin{aligned} Ans&=\sum_{S\sube N}\sum_{P\sube U}[f(P)=S]\sum_{Q\sube U}[f(Q)=S][P\cup Q=\emp]val(P)val(Q)\\ &=\sum_{S\sube N}\sum_{T_P\supe S}(-1)^{|S|-|T_P|}\sum_{T_Q\supe S}(-1)^{|S|-|T_Q|}\sum_{P\sube U}[f(P)\supe T_P]\sum_{Q\sube U}[f(Q)\supe T_Q][P\cup Q=\emp]val(P)val(Q)\\ &=\sum_{T_P\sube N, T_Q\sube N}(-1)^{|T_P|+|T_Q|} 2^{|T_P\cap T_Q|}\sum_{P\sube U}\sum_{Q\sube U}[f(P)\supe T_P][f(Q)\supe T_Q][P\cup Q=\emp]val(P)val(Q) \end{aligned}$$

• 若 $x\supe T_P\cup T_Q$：在 $U,V$ 中都可以选；
• 否则，若 $x\supe T_P$：只在 $U$ 中可选；
• 否则，若 $x\supe T_Q$：只在 $V$ 中可选；
• 否则不可选。

$$\begin{aligned} Ans&=\sum_{T_P\sube N, T_Q\sube N}(-1)^{|T_P|+|T_Q|} 2^{|T_P\cap T_Q|}\sum_{P\sube U}\sum_{Q\sube U}[f(P)\supe T_P][f(Q)\supe T_Q][P\cup Q=\emp]val(P)val(Q)\\ &=\sum_{T_P\sube N, T_Q\sube N}(-1)^{|T_P|+|T_Q|} 2^{|T_P\cap T_Q|}\left(\prod_{x\supe T_P}(a_x+1)\right)\left(\prod_{x\supe T_Q}(a_x+1)\right)\left(\prod_{x\supe T_P\cup T_Q}\frac{2a_x+1}{(a_x+1)^2}\right) \end{aligned}$$ $$\begin{aligned} Ans&=\sum_{T_P\sube N, T_Q\sube N}(-2)^{|T_P|}(-2)^{|T_Q|} 2^{-|T_P\cup T_Q|}\left(\prod_{x\supe T_P}(a_x+1)\right)\left(\prod_{x\supe T_Q}(a_x+1)\right)\left(\prod_{x\supe T_P\cup T_Q}\frac{2a_x+1}{(a_x+1)^2}\right)\\ &=\sum_{T\sube N}2^{-|T|}\left(\prod_{x\supe T}\frac{2a_x+1}{(a_x+1)^2}\right)\sum_{T_P,T_Q}[T_P\cup T_Q=T]\left((-2)^{|T_P|}\left(\prod_{x\supe T_P}(a_x+1)\right)\right)\left((-2)^{|T_Q|}\left(\prod_{x\supe T_Q}(a_x+1)\right)\right) \end{aligned}$$