计数

图

下文默认有标号

DAG生成子图计数

\(DAG\) 中总会还有入度为 \(0\) 的点，所以每次删去这些节点会得到一个同为 \(DAG\) 的子结构，考虑实现这样的转移。

令 \(dp_s\) 表示子集 \(s\) 的答案。全集为当前 \(s\) 时，\(f_t\) 表示 \(t\) 中点恰为被选中的入度为 \(0\) 的点的方案数，\(g_t\) 为钦定 \(t\) 中点入度一定为 \(0\) 的方案数。

有：

\[g_t=\sum_{t\subseteq r}f_r \]

考虑反演：

\[f_t=\sum_{t\subseteq r}(-1)^{|r|-|t|}g_r \]

与 \(dp\) 的关系：

\[dp_s=\sum_{t\subseteq s,t\neq \emptyset }f_t\\ g_t=2^{E_{t,s-t}}dp_{s-t} \]

整合一下：

\[\begin{align*} dp_s &= \sum_{t\subseteq s,t\neq \emptyset } \sum_{t\subseteq r}(-1)^{|r|-|t|}g_r\\ &=\sum_{r\subseteq s,r\neq \emptyset }(-1)^{|r|}g_r \sum_{t\subseteq r,t\neq \emptyset }(-1)^{|t|}\\ &=\sum_{r\subseteq s,r\neq \emptyset }(-1)^{|r|+1}g_r\\ &=\sum_{r\subseteq s,r\neq \emptyset }(-1)^{|r|+1}2^{E_{r,s-r}}dp_{s-r}\\ \end{align*} \]

\(O(3^n)\) 子集枚举转移。

有向图强连通生成子图计数

直接刻画强连通是困难的，考虑容斥。对于一个不是强连通的图在缩点之后一定是点数大于 \(1\) 的 \(DAG\) 。

考虑与 \(DAG\) 计数相同的方式，枚举入度为 \(0\) 的点。

令 \(dp_s\) 表示子集 \(s\) 的答案，\(g_t\) 表示将 \(t\) 中的点缩成若干个入度为 \(0\) 的点的方案数。

有：

\[dp_s=2^{E_{s,s}}-\sum_{t\subseteq s}(-1)^{scc+1}g_t2^{E_{s-t,s-t}+E_{t,s-t}}\\ \]

注意上面的容斥系数是 \(t\) 中划分的连通块的个数，这个值是不确定的，常用的手段是将其带入 \(g\) 的状态中，每次加连通块时计算 \(-1\) 的贡献。

考虑 \(g\) 的转移，为了避免加入顺序不同导致同一种划分被计算多次，通常在当前轮加入 \(lowbit(s)\) 所属的连通块：

\[g_s=dp_s-\sum_{t\subset s,lowbit(t)=lowbit(s)}dp_tg_{s-t} \]

\(g\) 与 \(dp\) 看似是相互转移的，但注意到，\(dp\) 后面减的部分应当是 \(s\) 无法连通的容斥出来的和，当 \(t=s\) ，\(t\) 中只有一个连通块时，\(s\) 是连通的，也就是 \(g_s\) 中第一项 \(dp_s\) 的贡献是不应该被计算的。 \(g\) ，在转移 \(dp\) ，最后再将 \(dp_s\) 加到 \(g_s\) 上就行了。

树

https://codeforces.com/contest/2164/problem/F1

考虑从下往上合并，对于点 \(u\) ，将 \(u\) 到根的所有点作为隔板，当前的合并操作就是将 \(u\) 的所有儿子插入隔板中，再把 \(u\) 从隔板变成结点。隔板与隔板之间的所有点称之为一个块，当不同儿子插入同一个块中时，会计算一个排列的组合数。\(u\) 节点变为结点时会合并块 \(a_u\) 和 \(a_u+1\) 到块 \(a_u\) 。上述过程只需要维护到每个点时，每个块的大小，总时间复杂度 \(O(n^2)\) 。

序列

AT_agc058_d

常规的容斥使用钦定个数，但是有时候个数并不是很好求，比如在此题中，我们需要钦定的每个是长度为 \(3\) 的串，当钦定的两个相邻时，可能会产生额外的串。

对于此类钦定的点为串且串与串这件会产生额外贡献的情况，把相邻的串合并为一个点，序列变成若干个段，每个段包含若干个串，且段与段相邻则要求不能产生合法的串，如此就把钦定点的个数就变成了段的个数，可以对每个段的起点容斥。