自动搬运

查看原文

来自洛谷，原作者为

	yxzy4615 **

搬运于2025-08-24 22:22:47，当前版本为作者最后更新于2021-10-14 08:48:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目描述

给定$n$个点，$m$条边的有向无环图。不保证图联通。 $q$次询问，每次给出$k$和$k$个互不相同的数$c_i$ ，求出如果去掉这$k$个点，整个有向无环图将剩余多少条链。答案对$10^9+7$取模。每次询问独立。

• “链”的定义是：我们设一条长度为$p$的链的路径为$w_0\to w_1\to\cdots\to w_{p-1}\to w_p$ ，则应满足$w_0$入度为$0$，$w_p$出度为$0$。你可以将其理解为一条食物链。

• 两条链是“不同的”，当且仅当它们的长度不同，或者经过的点集不同。

• 需要特别注意的是，删去某些点后新产生的链不计入答案。 例如$1\to 2\to 3\to 4$一图中，有$1$条链$1\to 2\to 3\to 4$。如果去掉$2$号点，则剩余$0$条链。

数据范围

• Subtask 1（1 point）：给定的图是一条链。
• Subtask 2（14 points）：$n,q\leq 10$。
• Subtask 3（20 points）：$q\leq 10^3$。
• Subtask 4（17 points）：$k=1$。
• Subtask 5（18 points）：$k=2$。
• Subtask 6（30 points）：无特殊限制。

对于$100\%$的数据：$2\leq n\leq 2\times 10^3$，$1\leq m\leq \min(\frac{n\times(n-1)}{2},2\times 10^4)$，$1\leq q\leq 5\times 10^5$

所有询问满足：$1\leq \sum k\leq 2\times 10^6$，$0\leq k\leq \min(n,15)$，$1\leq c_i\leq n$。保证 $c_i$互不相同。

题目分析

$Subtask1$

很明显，如果 $k=0$ 就只有一条链，否则就没有。

$Subtask2-3$

标记删掉的点，暴力去跑图。

设$f_i$表示以$i$结尾的链数，转移显然：

$$∀(u,v),f_v\leftarrow f_u+f_v$$

时间复杂度$O(qm)$。

$Subtask4$

$k=1$的情况下，考虑删去的点会对答案产生多少贡献。

拿样例作分析：

入度为$0$的点是$3$，出度为$0$的点是$5$。手玩找出$f_i$。

$ \begin{matrix} i & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ f_i & 1 & 2 & 1 & 6 & 13 & 4 & 1 \end{matrix} $

再找出每个点到出度为$0$的点的方案数$n\!f_i$。

$ \begin{matrix} i & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ n\!f_i & 3 & 3 & 13 & 1 & 1 & 2 & 4 \end{matrix} $

手玩答案后汇总得：

$ \begin{matrix} i & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ f_i & 1 & 2 & 1 & 6 & 13 & 4 & 1\\ n\!f_i & 3 & 3 & 13 & 1 & 1 & 2 & 4\\ ans_i & 10 & 7 & 0 & 7 & 0 & 5 & 9 \end{matrix} $

设$s$为出度为$0$的$f_i$的和，发现$ans_i=s-f_i\times n\!f_i$。

$O(m)$预处理，$O(1)$查询，总复杂度$O(q+m)$。

$Subtask5$

对于$k=2$，直接用 $ans=s-f_i\times n\!f_i-f_j\times n\!f_j$计算可能会出问题，因为同时经过$i,j$的链会被重复计算，考虑两点容斥。

设$d_{i,j}$表示在原图上$i \to j$的方案数，还是通过样例：

$ \begin{matrix} d_{i,j} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & i\\ 1 & 1 & 0 & 0 & 2 & 3 & 1 & 0 & \\ 2 & 0 & 1 & 0 & 1 & 3 & 1 & 0 & \\ 3 & 1 & 2 & 1 & 6 & 13 & 4 & 1 & \\ 4 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & \\ 5 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & \\ 6 & 0 & 0 & 0 & 1 & 2 & 1 & 0 & \\ 7 & 0 & 1 & 0 & 2 & 4 & 1 & 1 & \\ j & \end{matrix} $

可以发现一个性质:若 $i\ne j$，则 $d_{i,j}\times d_{j,i}=0$。显然成立。

• 如果 $d_{i,j}=d_{j,i}=0$，代表 $i,j$到出度为$0$的点的路径不相交，直接用 $ans=s-f_i\times n\!f_i-f_j\times n\!f_j$ 计算即可。
• 如果 $d_{i,j}\ne 0$，代表 $i,j$到出度为$0$的点的路径中 $i$包含 $j$，重复路径就是 $f_i\times d_{i,j}\times n\!f_j$，用 $ans=s-f_i\times n\!f_i - (f_j - f_i \times d_{i,j})\times n\!f_j$ 计算即可。
• 如果 $d_{j,i}\ne 0$。用 $ans=s-f_i\times (n\!f_i - f_j \times d_{j,i})- f_j\times n\!f_j$ 计算即可，同上。

所以，总计算式为：

$$ans=s-(f_i-f_j\times d_{j,i})\times n\!f_i - (f_j - f_i \times d_{i,j})\times n\!f_j $$

$O(nm)$预处理，$O(1)$查询，总复杂度$O(nm+q)$。

$Subtask6$

到此，思路已经全部出来了，将$k=2$的情况扩展。对所有删去的点的每个点对 $(i,j)$，如果$i$能到达$j$，就往$i\to j$连一条的边，然后再拓扑排序一遍：对于每个点$i$的出边 $p$ 将 $f_p\leftarrow f_p-f_i\times d_{i,p}$ 。最后统计答案，即

$$ans=s-\sum\limits_{i=1}^kf_{c_i}\times n\!f_{c_i}$$

这个可以通过预处理拓扑序避免每次询问再跑一遍拓扑，即根据拓扑序排序后进行容斥。

$O(nm)$预处理，$O(k^2)$查询，总复杂度$O(nm+k\sum k)$。

参考代码