题目大意

给定一个连通无向图 $G$，计算有多少个图 $G'$ 满足对于所有节点 $a$ 和步数 $b$，从节点 $1$ 到 $a$ 是否存在长度为 $b$ 的路径在 $G$ 和 $G'$ 中相同。答案对 $10^9+7$ 取模。

核心思路

关键观察

1. 距离奇偶性：每个节点有两个关键距离值 $dis[i][0]$ 和 $dis[i][1]$，分别表示从节点 1 出发的偶数和奇数最短距离
2. 节点分类：按 $(d_0, d_1)$ 对节点分组，其中 $d_0 \le d_1$
3. 边约束：边的存在性必须保持所有节点的距离奇偶性不变

算法框架

1. 预处理

// 计算组合数 C(n, k)
// 计算 2 的幂次 pw[i] = 2^i mod MOD
// 计算 (2^i - 1)^j mod MOD

2. BFS 计算最短距离

使用 BFS 同时计算每个节点的偶数和奇数最短距离。

3. 特殊情况处理

如果节点 1 没有奇数距离路径（即图是二分图），则：

• 节点按距离 $d_0$ 分层
• 方案数 = $\prod_{i} (2^{cnt_{i-1}} - 1)^{cnt_i} \times 2^{\text{其他允许的边}}$

4. 一般情况处理

对于包含奇数环的图：

• 按 $i = d_1$ 从 $dis[1][1]$ 到 $2n$ 枚举（步长为 2）
• 对每个 $i$，使用动态规划计算该层的方案数

动态规划核心

状态设计

dp[k] 表示在处理当前层时，某种节点分配的方案数。

状态转移

对于每对 $(j, i-j)$ 的节点组：

• c1 = cnt[j-1][i-j+1]：上一层的节点数
• c2 = cnt[j][i-j]：当前层的节点数

转移时使用容斥原理计算合法的边选择方案：

for (int k2 = 0; k2 <= k; k2++) {
    int tmp = 1ll * c[k][k2] * pw1[c1 - k2][k1] % mod 
              * pw[(c1 - k2) * (c2 - k1)] % mod;
    if (k2 & 1) tmp = mod - tmp;
    res = (res + tmp) % mod;
}

最终计算

对于最后一层（$i/2, i/2+1$）的特殊处理：

• 使用容斥计算该层内部的边选择方案
• 与之前的结果相乘得到总方案数

复杂度分析

• 时间复杂度：$O(T \cdot n^4)$，但由于数据范围限制（$n \le 100$ 且 $\sum n^2 \le 10^5$），实际可接受
• 空间复杂度：$O(n^2)$

算法亮点

1. 分层处理：按距离值将图分层，简化计数问题
2. 容斥原理：排除不合法的边选择方案
3. 动态规划：高效计算复杂约束下的方案数
4. 模运算优化：预处理幂次和组合数，提高效率

总结

本题是图论与组合计数结合的经典问题，通过分析图的距离结构，将复杂的图同构计数问题转化为分层动态规划问题。