Counting Graphs

题目描述

Bessie 有一个连通的无向图 $G$，包含 $N$ 个标号为 $1\ldots N$ 的点以及 $M$ 条边（$2\le N\le 10^2, N-1\le M\le \frac{N^2+N}{2}$）。$G$ 可能包含自环（从一个点连回自身的边），但不包含重边（连接同一对端点的多条边）。 令 $f_G(a,b)$ 为一个布尔函数：对每个 $1\le a\le N$ 和 $0\le b$，当且仅当存在一条从点 $1$ 到点 $a$ 的路径，且该路径恰好经过 $b$ 条边时，$f_G(a,b)$ 为真；否则为假。如果某条边被多次经过，则在计数中按经过次数重复计入。 Elsie 想要模仿 Bessie。具体而言，她想构造一个无向图 $G'$，使得对所有的 $a$ 和 $b$ 都有 $f_{G'}(a,b)=f_G(a,b)$。 你的任务是计算 Elsie 可能构造出的不同图 $G'$ 的数量，并对 $10^9+7$ 取模。与 $G$ 相同，$G'$ 可以包含自环但不包含重边（也就是说，在 $N$ 个带标号的点上总共有 $2^{\frac{N^2+N}{2}}$ 种不同的图）。 每个输入包含 $T$（$1\le T\le \frac{10^5}{4}$）个测试用例，彼此独立求解。保证所有测试用例的 $N^2$ 之和不超过 $10^5$。

输入格式

第一行包含整数 $T$，表示测试用例数量。 每个测试用例的第一行包含整数 $N$ 和 $M$。 接下来 $M$ 行每行包含两个整数 $x$ 和 $y$（$1\le x\le y\le N$），表示在 $G$ 中存在一条连接 $x$ 与 $y$ 的边。 为了便于阅读，相邻测试用例之间用空行分隔。

输出格式

对每个测试用例，输出不同的 $G'$ 的数量对 $10^9+7$ 取模后的结果，每个结果占一行。

1

5 4
1 2
2 3
1 4
3 5

3

7

4 6
1 2
2 3
3 4
1 3
2 4
1 4

5 5
1 2
2 3
3 4
4 5
1 5

5 7
1 2
1 3
1 5
2 4
3 3
3 4
4 5

6 6
1 2
2 3
3 4
4 5
5 6
6 6

6 7
1 2
2 3
1 3
1 4
4 5
5 6
1 6

10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

22 28
1 2
2 3
3 4
4 5
5 6
6 7
1 7
1 8
3 9
8 10
10 11
10 12
10 13
10 14
11 15
12 16
13 17
14 18
9 15
9 16
9 17
9 18
15 19
19 20
15 20
16 21
21 22
16 22

45
35
11
1
15
371842544
256838540

提示

在第一个测试用例中，$G'$ 可以等于 $G$，或者为下面两个图之一： 5 4 1 2 1 4 3 4 3 5 5 5 1 2 2 3 1 4 3 4 3 5 这些是一些更大的测试用例。请确保输出答案对 $10^9+7$ 取模。注意倒数第二个测试用例的答案为 $2^{45}\pmod{10^9+7}$。 计分： 输入 3 中的所有测试用例满足 $N\le 5$。 输入 4-5 中的所有测试用例满足 $M=N-1$。 对于输入 6-11 中的所有测试用例，若并非对所有 $b$ 都有 $f_G(x,b)=f_G(y,b)$，则存在某个 $b$ 使得 $f_G(x,b)$ 为真而 $f_G(y,b)$ 为假。 输入 12-20 中的测试用例没有额外限制。 题目致谢：Benjamin Qi

标签: USACO|2021|Platinum

来源

USACO|2021|Platinum