计数问题¶

不相交路径¶

题意¶

一个有向无环图，给定四个点 $a,b,c,d$，求出有多少对路径 ($a\to b, c\to d$) 满足两条路径没有公共点。($1 \le n\le 200$，$1 \le m \le 20000$)

题解¶

先 $O(nm)$ 处理出任意两点间路径数量 $f_{i,j}$，枚举起点赋值为 $1$ 然后按拓扑序向后转移即可。

设所求答案为 $\textit{ans}$，两条路径 $a \to b,c \to d$ 有交点的对数为 $\textit{sum}$，运用补集转化，则有： $$ \textit{ans} = f_{a,b} f_{c,d}-\textit{sum} $$ 设 $g_x$ 为两条路径 $a \to x,c \to x$ 没有交点的对数，那么枚举第一个相交的点，有： $$ \textit{sum} = g_x f_{x,b} f_{x,d} $$ 再次运用补集转化，枚举第一个相交的点，有： $$ g_x = f_{a,x} f_{c,x} - \sum_y g_y f^2_{y,x} $$ 按照拓扑序计算即可进行转移，总时间复杂度 $O(nm+n^2)$。

连通图计数¶

题意¶

$n$ 个点带标号的连通图有多少个。($1 \le n \le 2000$)

题解¶

使用补集转化，对于不连通的方案，枚举 $1$ 号点所在连通块的大小，有： $$ f_i = 2^{\binom{n}{2}} - \sum_{j=1}^{i-1}\binom{i-1}{j-1}f_j 2^{\binom{i-j}{2}} $$ 时间复杂度 $O(n^2)$。

二分图计数¶

题意¶

$n$ 个点带标号的二分图有多少个。($1 \le n \le 2000$)

题解¶

先算出 $i$ 个点带标号的二分图的黑白染色方案之和 $g_i$，相当于选一些点当黑点，然后黑点白点之间的边任意连： $$ g_i=\sum_{j=0}^{i\binom{i}{j}2}{j(i-j)} $$