P6651

yxzy4615 · 2021-10-14 08:48:40 · 题解

题目描述

给定n个点，m条边的有向无环图。不保证图联通。

，求出如果去掉这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结尾的链数，转移显然：

时间复杂度O(qm)。

Subtask4

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

\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}

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

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

可以发现一个性质:若 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 计算即可，同上。

所以，总计算式为：

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

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