【NOIP2024】遗失的赋值 - 题目

小 F 有 $n$ 个变量 $x_{1}, x_{2}, \dots, x_{n}$ 。每个变量可以取 $1$ 至 $v$ 的整数取值。

小 F 在这 $n$ 个变量之间添加了 $n - 1$ 条二元限制，其中第 $i$ （ $1 \leq i \leq n - 1$ ）条限制为：若 $x_{i} = a_{i}$ ，则要求 $x_{i + 1} = b_{i}$ ，且 $a_{i}$ 与 $b_{i}$ 为 $1$ 到 $v$ 之间的整数；当 $x_{i} \neq a_{i}$ 时，第 $i$ 条限制对 $x_{i + 1}$ 的值不做任何约束。除此之外，小 F 还添加了 $m$ 条一元限制，其中第 $j$ （ $1 \leq j \leq m$ ）条限制为： $x_{c_{j}} = d_{j}$ 。

小 F 记住了所有 $c_{j}$ 和 $d_{j}$ 的值，但把所有 $a_{i}$ 和 $b_{i}$ 的值都忘了。同时小 F 知道：存在给每一个变量赋值的方案同时满足所有这些限制。

现在小 F 想知道，有多少种 $a_{i}, b_{i}$ （ $1 \leq i \leq n - 1$ ）取值的组合，使得能够确保至少存在一种给每个变量 $x_{i}$ 赋值的方案可以同时满足所有限制。由于方案数可能很大，小 F 只需要你输出方案数对 $10^{9} + 7$ 取模的结果。

输入格式

本题包含多组测试数据。

输入的第一行包含一个整数 $T$ ，表示测试数据的组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含三个整数 $n, m, v$ ，分别表示变量个数、一元限制个数和变量的取值上限。

接下来 $m$ 行，第 $j$ 行包含两个整数 $c_{j}, d_{j}$ ，描述一个一元限制。

输出格式

对于每组测试数据输出一行，包含一个整数，表示方案数对 $10^{9} + 7$ 取模的结果。

样例 #1

样例输入 #1

样例输出 #1

4
3
0

限制与约定

【数据范围】

对于所有的测试数据，保证：

$1 \leq T \leq 10$ ，
$1 \leq n \leq 10^{9}$ ， $1 \leq m \leq 10^{5}$ ， $2 \leq v \leq 10^{9}$ ，
对于任意的 $j$ （ $1 \leq j \leq m$ ），都有 $1 \leq c_{j} \leq n$ ， $1 \leq d_{j} \leq v$ 。

测试点	$n \leq$	$m \leq$	$v \leq$	特殊性质
$1, 2$	$6$	$6$	$2$	无
$3$	$9$	$9$	$2$	无
$4, 5$	$12$	$12$	$2$	无
$6$	$10^{3}$	$1$	$10^{3}$	无
$7$	$10^{5}$	$1$	$10^{5}$	无
$8, 9$	$10^{9}$	$1$	$10^{9}$	无
$10$	$10^{3}$	$10^{3}$	$10^{3}$	A
$11$	$10^{4}$	$10^{4}$	$10^{4}$	A
$12$	$10^{5}$	$10^{5}$	$10^{5}$	A
$13$	$10^{4}$	$10^{3}$	$10^{4}$	B
$14$	$10^{6}$	$10^{4}$	$10^{6}$	B
$15, 16$	$10^{9}$	$10^{5}$	$10^{9}$	B
$17$	$10^{4}$	$10^{3}$	$10^{4}$	无
$18$	$10^{6}$	$10^{4}$	$10^{6}$	无
$19, 20$	$10^{9}$	$10^{5}$	$10^{9}$	无

特殊性质 A：保证 $m = n$ ，且对于任意的 $j$ （ $1 \leq j \leq m$ ），都有 $c_{j} = j$ 。

特殊性质 B：保证 $d_{j} = 1$ 。

时间限制： $1s$

空间限制： $512MB$

Universal Online Judge

UOJ