n\le 15

· · 个人记录

状压图计数

### DAG 子图计数 找出子结构。 我们可以把 DAG 的第一层拆出来，也就是入度为 $0$ 的点。 设只考虑 $S$ 内的点的方案数为 $f_S$，子集容斥，考虑入度为 $0$ 的点的集合恰好为 $T$。 $$ \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} $$ ### 强连通子图计数 别名主旋律。 $\text{强连通子图数}=\text{总子图数}-\text{非强连通子图数}$。 设 $f_S$ 为点集 $S$ 的答案，$g_S$ 为把点集 $S$ 缩点后为若干个单点的方案数，仍然是枚举 DAG 中入度为 $0$ 的点集，套用上面的结果，则有： $$ 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)} $$ 注意这里分出来第一层之后后面怎么样已经不用管了，还必须去掉 $T=S,T\;缩点后点数=1$ 的情况。 把容斥系数写到 $g$ 里面，即一个块为 $1$，每分一个乘上 $-1$ 的系数。 找一个代表元，强制 $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} $$ 注意减去的是非连通子图，当 $T=S$ 时，$g_S$ 不能包含只分成一块的方案，正好解决了转移顺序的问题。 ### 岁月 主要讲 C 性质，剩下的在 ex 里面。 题面就不写了，下面仍然是按照概率来计算。 考虑能到达所有点的点集恰好为 $P$，全集为 $U$，需要满足： - $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)} $$ 三部分独立，可以直接乘起来。 考虑 $f_U$ 从哪里贡献过来：选定一个 $S\supe P$，考虑它上面的 $1$，经过一条 $S\to U$ 的路径，乘上系数 $2^{-\w(T,S\sm T)}$，贡献到 $f_U$。 所以可以倒过来转移，再做超集和。 :::info[ex] 最小生成树的结论，转成对于每种权值，都在把一些连通块合并起来。终点在连通块的根集中的边才有用。 所以 $\gdef\ww{cross'}\ww(S,T)=\w(\{u\mid\exist v\in S,u,v\,\text{在同一连通块中}\},T)

还是分成三部分：

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

重塑时光

会上面的东西之后就很简单了，建议降紫。

\xdef\noe#1#2{[\w(#1,#2)=0]}

首先去掉概率，总共的方案数为 (n+k)!。由于判定的条件只和这些选出来的非空集合有关，考虑最后有 s 个非空集合，则有方案数 \frac{1}{n!(n+1)^{\overline{k}}}\times k!\times s!\times\binom{k+1}{s}，四个项的意义都比较清晰。

剩下的就是在一个 dag 上面划分 s 个集合，满足：每个集合之内都要是拓扑序排列；集合之间的边还是一个 dag。

直接套用主旋律的容斥。

设 f_{i,S} 表示分了 i 个集合，分走了 S 内的点的方案数，g_{i,S} 类似，h_S 处理集合内的拓扑序问题（计算直接枚举第一个点）。

\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} ### 最小边双/点双/强连通生成子图 耳分解。以后再补。 **由于无向图的对称性，很多东西在无向图上都可以运用集合幂级数技术从 $3^n$ 优化到 $2^npoly(n)$。** ### 边双/点双计数 ### Message Spread ## 集合幂级数 https://www.luogu.com.cn/article/46x8prtw > 反演本身是一种容斥，通常把所求的东西的自由度扩大，但是却能将“恰好”、“一一对应”的这一类奇怪的限制给去掉，从而使得在计数角度方面的限制与状态缩小、化简。 #### 容斥原理 有一些元素和 $n$ 个限制，满足第 $i$ 个限制的元素集合为 $S_i$，则： 满足所有限制的集合大小： $$ \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| $$ #### 子集/超集反演 设 $f(S)$ 为最终状态为 $S$ 的答案，$g(S)$ 为最终状态为 $S$ 的**子集**时的答案，即有： $$ g(S)=\sum_{T\sube S}f(T) $$ 则我们有： $$ f(S)=\sum_{T\sube S}(-1)^{|S|-|T|}g(T) $$ 设 $f(S)$ 为最终状态为 $S$ 的答案，$g(S)$ 为最终状态为 $S$ 的**超集**时的答案，即有： $$ g(S)=\sum_{T\supe S}f(T) $$ 则我们有： $$ f(S)=\sum_{T\supe S}(-1)^{|S|-|T|}g(T) $$ 证明都是简单的。 #### 二项式反演 也就是只关心集合的大小，所以一样有所谓的子集和超集，常用的是超集。 超集： 设 $f(x)$ 为**恰好**满足 $x$ 个限制的答案，$g(x)$ 为**钦定（至少）** 满足 $x$ 个限制的答案。 $$ g(x)=\sum_{x\le i}\binom{i}{x}f(i) $$ 一个方案会贡献 $\binom{|S|}{x}$ 次。 则我们有： $$ f(x)=\sum_{x\le i}(-1)^{x-i}\binom{i}{x}g(i) $$ 子集： 略去。 形式非常简单，什么时候添加 $(-1)^{x-i}$ 只用看大小就好，上面的子集反演也一样。 是不是应该从 fwt 说起？ ### NOI2025 集合 因为 $P\cap Q=\emp$，有 $val(P\cup Q)=val(P)val(Q)$。 定义 $N=\{0,1,\dots,n-1\}$，$U=\{0,1,\dots,2^n-1\}$。区分什么时候是全集。 $$ \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} $$ $f$ 相当于钦定一些二进制位必须全选，剩下的至少要不选一个，这不好处理。考虑把至少不选一个容斥掉，也就是超集反演。 这里反演的时候要对 $P$ 和 $Q$ 分开反演两次（可以理解为先对 $P$ 反演，再对 $Q$ 反演，$Q$ 的时候全集会变），而不是一起做，不然 $g$ 没有实际意义，还是不好做。 $$ \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\in U$： - 若 $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} $$ 明显是一个 or 卷积，那么这题就做完了，怎么样很简单吧。 注意有一个除 $0$ 的问题，那由于最后 $0$ 的次数必定不小于 $0$，在加法的时候只保留最低次的即可。