#P17203. [2025年南外]食物链

    ID: 16362 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高拓扑序计数路径DAG 动态规划补集计数

[2025年南外]食物链

Description

小 A 在研究生态系统的稳定性。

他认为一个生态系统可以被抽象成一张有向无环图 G=(V,E)G=(V,E),VV 中的每个节点 uu 代表一种生物,EE 中的每一条有向边 u→vu\to v 表示 u,vu,v 之间存在捕食与被捕食的关系:uu 被 vv 捕食。

小 A 定义一条食物链为:从一个入度为 00 的节点 p0p_0 到一个出度为 00 的节点 pwp_w 所形成的路径 p0→p1→⋯→pw−1→pwp_0\to p_1\to \cdots \to p_{w-1}\to p_w。注意食物链可能退化成一个点,即 p0=pwp_0=p_w。此外,两种生物之间的食物链可能有多条。

为了测试生态系统的稳定性,小 A 会多次删去若干个节点以模拟特定生物灭绝的情况。他认为生态系统中剩余的食物链越多,则其越稳定。

但由于整个生态系统太复杂了,就算一些生物灭绝后,剩余的食物链数量仍然是巨大的。他想请你帮他求出每次删去一些特定节点后剩余的食物链条数,对 109+710^9+7 取模。注意这个过程会产生新的入度或出度为 00 的节点,但这些新产生的食物链不计入在内。

形式化地,给出一张点数为 nn,边数为 mm 的 DAG。定义路径集合 SS 为所有合法路径 P:p0→p1→⋯→pw−1→pwP:p_0\to p_1\to\cdots\to p_{w-1}\to p_w 所形成的集合。合法路径可以是一个点,但需要满足 p0p_0 的入度为 00,pwp_w 的出度为 00。qq 次询问给出 kk 和 kk 个互不相同的数 cic_i,请你求出删去所有 cic_i 后,整个 DAG 剩余的合法路径条数,新增的合法路径不计入答案。即求出 $|\{P\mid P\in S\land \forall p_j\in P, p_j\notin\{c_i\}\}|\bmod (10^9+7)$

Input Format

第一行两个整数 n,mn,m,分别表示点的个数和边的条数。

接下来 mm 行,每行两个整数 u,v(u≠v)u,v(u\neq v),表示 u→vu\to v 之间有一条有向边。

第 m+2m+2 行一个整数 qq,表示询问个数。

接下来 qq 行,每行先是一个整数 kk,表示去掉的点的个数;然后 kk 个整数 cic_i,表示去掉的点的编号。

Output Format

共 qq 行,每行表示该次询问的答案对 109+710^9+7 取模后的值。

Sample

样例 1 输入

7 14
3 2
4 5
2 5
2 6
3 1
3 5
3 7
3 6
6 4
1 4
6 5
1 6
7 2
7 4
7
3 2 4 6
2 4 6
2 2 5
2 1 4
0
1 4
1 6

样例 1 输出

1
3
0
6
13
7
5

样例 1 说明

DAG 如图:

询问 11:如果去掉 2,4,62,4,6,则剩余 11 条链:3→53\to 5。

询问 22:如果去掉 4,64,6,则剩余 33 条链:3→53\to 5,3→2→53\to 2\to 5,3→7→2→53\to 7\to 2\to 5。

询问 77:如果去掉 66,则剩余 55 条链:3→53\to 5,3→2→53\to 2\to 5,3→7→2→53\to 7\to 2\to 5,3→1→4→53\to 1\to 4\to 5,3→7→4→53\to 7\to 4\to 5。

样例 2 输入

233 1
1 2
7
0
1 10
2 10 40
2 15 23
1 1
1 2
2 1 2

样例 2 输出

232
231
230
230
231
231
231

[附加文件](file://down.zip)

Hint

对于 100%100\% 的数据:2≤n≤2×1032\leq n\leq 2\times 10^3,$1\leq m\leq \min(\frac{n\times(n-1)}{2},2\times 10^4)$,1≤q≤5×1051\leq q\leq 5\times 10^5。

所有询问满足:1≤∑k≤2×1061\leq \sum k\leq 2\times 10^6,0≤k≤min⁡(n,15)0\leq k\leq \min(n,15),1≤ci≤n1\leq c_i\leq n。保证 cic_i 互不相同。

  • Subtask 1(1 point):给定的图是一条链。
  • Subtask 2(14 points):n,q≤10n,q\leq 10。
  • Subtask 3(20 points):q≤103q\leq 10^3。
  • Subtask 4(20 points):k=1k=1。
  • Subtask 5(20 points):k=2k=2。
  • Subtask 6(25 points):无特殊限制。

请注意 IO 优化。