这道题要求计算在城市网格（夜间道路构成树）中选择办公室的方案数，需满足 “白天与夜间巡视的最短长度相同”，且根据T的不同（1、2、3）有不同的办公室数量限制。核心思路是先分析白天与夜间巡视长度相等的条件，再针对不同 T分类计算合法方案。

问题分析

1.核心前提：白天与夜间的巡视长度

• 夜间道路：题目明确是一棵包含 $N×M$个节点的树，任意 $K$个办公室（节点）的巡视路径是树中这 $K$个节点的最小生成树（MST）的两倍（因为巡视需从起点出发遍历所有节点并返回，即 “欧拉回路”，树的 MST 边数为 $K−1$，总长度为 $2×(K−1)$）。
• 白天道路：是完整的网格图（横向、纵向道路均可用），任意 $K$个办公室的巡视最短长度是其最小包围矩形的周长（因为网格图中遍历矩形内所有目标节点的最短路径为周长，无需绕路）。
• 相等条件：设$K$个办公室的最小包围矩形周长为 $C$，则需满足 $C=2×(K−1)$。进一步推导可得：这$K$个办公室必须构成 “链状结构”—— 即所有节点在一条直线上（横向或纵向），且相邻节点在网格中直接相连（无间隙），此时包围矩形的周长恰好等于树中 MST 长度的两倍。 2.不同$T$的方案计数目标
• $T=1$：统计所有 “至少包含 2 个办公室” 且满足条件的非空子集（方案数为所有合法链的子集数之和，需排除重复计数）。
• $T=2$：统计所有 “恰好包含 2 个办公室” 的合法方案（即所有在网格中直接相邻、且在夜间树中也相邻的节点对，因为 2 个节点的链就是直接相连的边）。
• $T=3$：统计所有 “恰好包含 3 个办公室” 的合法方案（即所有长度为 2 的链，3 个节点在一条直线上且相邻节点直接相连）。

解题思路

针对 $T = 1、2、3$分别设计计算逻辑，核心是预处理网格中的 “连续链” 信息，再基于预处理结果快速统计合法方案。

1. 预处理：链信息与辅助数组 首先解析输入的夜间道路，构建网格中每个节点的相邻边（上、下、左、右），再通过 4 个方向的遍历预处理关键信息：

• edge[i][j][o]：记录节点 (i,j)在方向 o（_u上、_d下、_l左、_r右）是否有夜间道路（1 表示有，0 表示无）。
• line[i][j][o]：记录节点 (i,j)在方向 o上的 “连续链长度”（例如 line[i][j][_r] 表示从(i,j)向右延伸的连续夜间道路长度）。

2. 分情况计算（$T = 1、2、3$） 情况 1：$T=2$(最简洁）

• 合法方案是 “在网格中相邻且夜间道路也相邻” 的节点对。
• 统计逻辑：遍历所有节点，检查其右、下两个方向（避免重复统计，如 (i,j)与 (i,j+1)只统计一次）的相邻节点是否存在夜间道路，若存在则计数加 1。
• 代码中通过 quad 数组的 rd（右下）和 dl（左下）方向统计横向、纵向的合法边，再减去重复计数的单个边，最终得到总方案数。 情况 2：$T=3$
• 合法方案是 “3 个节点构成直线链”（横向或纵向），且相邻节点均有夜间道路。
• 统计逻辑：基于 line 数组的连续链长度，遍历所有长度 ≥ $2$ 的链（横向或纵向），每个这样的链贡献 $(L−2)$个合法方案（例如长度为 $3$ 的链包含 $1$个 $3$ 节点方案，长度为 $4$ 的链包含 $2$ 个，以此类推）。
• 代码中通过 quad 数组的交叉链信息，结合 line 的连续长度，计算所有合法 $3$ 节点链的数量，同时排除重复计数的情况。 情况 3：$T=1$（最复杂）
  • 合法方案是 “所有至少包含 2 个节点的合法链的子集”，需避免同一子集被多个链重复计数（例如一个 3 节点链的子集，不能同时被其包含的 2 节点链子集重复统计）。
  • 统计逻辑：
  1. 遍历所有横向、纵向的连续链，计算每个链的 “有效子集数”（长度为$L$的链的子集数为 $2^L−1−L$ ，即排除空集和单个节点的子集）。
  2. 用动态规划数组 dp[i][j] 记录当前节点的累计子集数，避免重复计数（例如横向链和纵向链交叉时，只统计一次交叉区域的子集）。
  3. 最终通过容斥原理调整计数，减去重复计算的部分，得到所有合法子集的总数。 ### 代码详解 代码结构严格遵循 “预处理 → 分情况计算” 的逻辑，核心模块如下： 1. 预处理模块

// 1. 解析夜间道路，构建edge数组
rep(i, n) {
    cin >> s;
    rep(j, m) {
        ll x = s[j] - '0';
        if (x & 1)  // 有向上的道路（i,j）与（i-1,j）相连
            edge[i][j][_u] = edge[i-1][j][_d] = true;
        if (x & 2)  // 有向左的道路（i,j）与（i,j-1）相连
            edge[i][j][_l] = edge[i][j-1][_r] = true;
    }
}

// 2. 预处理line和quad数组（4个方向遍历，计算连续链长度）
// 方向1：右下（rd）—— 从右下往左上遍历
per(j, m) per(i, n) {
    if (edge[i][j][_r]) {  // 向右的连续链
        line[i][j][_r] = line[i][j+1][_r] + 1;
        quad[i][j][rd] += quad[i][j+1][rd] + 1;
    }
    if (edge[i][j][_d]) {  // 向下的连续链
        quad[i][j][rd] += quad[i+1][j][rd] + 1;
    }
}
// 方向2-4：左下（dl）、左上（lu）、右上（ur），逻辑类似，略...

2. $T=2$计算模块

if (k == 2) {
    rep(i, n) rep(j, m) {
        // quad[i][j][0]（rd）统计右下方向的横向+纵向链，quad[i][j][1]（dl）统计左下方向
        ans += quad[i][j][0] + quad[i][j][1];
        // 减去重复计数的单个边（line[i][j][0]是横向，line[i][j][1]是纵向）
        ans -= line[i][j][0] + line[i][j][1];
    }
    cout << ans % P;  // 模1e9+7，确保结果非负
}

3. $T=3$计算模块

if (k == 3) {
    rep(i, n) rep(j, m) {
        auto [r, d, l, u] = line[i][j];  // 横向（r/l）、纵向（d/u）的连续链长度
        auto [rd, dl, lu, ur] = quad[i][j];  // 4个象限的交叉链长度
        
        // 情况1：节点（i,j）未被使用，统计以其为“拐角”的3节点链
        ans += rd * l * u;    // 右下链 + 左链 + 上链
        ans += dl * u * r;    // 左下链 + 上链 + 右链
        ans += lu * r * d;    // 左上链 + 右链 + 下链
        ans += ur * d * l;    // 右上链 + 下链 + 左链
        // 减去重复计数的短链（长度不足3的情况）
        ans -= r * d * l;
        ans -= d * l * u;
        ans -= l * u * r;
        ans -= u * r * d;
        
        // 情况2：节点（i,j）被使用，统计以其为“中间节点”的3节点链
        ans += rd * lu;    // 右下链 + 左上链
        ans += ur * dl;    // 右上链 + 左下链
        // 减去重复计数的2节点链
        ans -= l * r;
        ans -= u * d;
    }
    cout << ans % P;
}

4. $T=1$计算模块

if (k == 1) {
    // 第一遍遍历：统计左上→右下方向的合法子集
    rep(i, n) rep(j, m) {
        auto [r, d, l, u] = line[i][j];
        dp[i][j] = 1;  // 初始状态：仅包含当前节点的子集（后续会调整）
        
        // 累加来自上方、左方的合法子集数
        if (edge[i][j][_u]) dp[i][j] += dp[i-1][j];
        if (edge[i][j][_l]) dp[i][j] += dp[i][j-1];
        
        // 计算上链和左链的子集贡献（(2^u -1)*(2^l -1) 是上链和左链的交叉子集数）
        long long e = (pw2[u] - 1) * (pw2[l] - 1) % P;
        ans += dp[i][j] + 2 * e;  // 累加基础子集数和交叉贡献
        // 更新dp：包含当前节点的所有合法子集数
        dp[i][j] = ((dp[i][j] + e) * 2 - 1) % P;
        // 累加右链和下链的扩展贡献
        ans += (dp[i][j] + 1) * (pw2[r] - 1) % P * (pw2[d] - 1) % P;
        ans %= P;
    }
    
    // 第二遍遍历：统计右上→左下方向的合法子集（避免遗漏横向/纵向链）
    rep(i, n) per(j, m) {
        // 逻辑与第一遍类似，仅方向改为右方和上方，略...
    }
    
    // 容斥调整：减去重复计数的空集和单个节点
    rep(i, n) rep(j, m) {
        auto [r, d, l, u] = line[i][j];
        ans += P - (pw2[r + d + l + u + 1] - 1);  // 减去超集重复
        ans += pw2[u] * (pw2[d + 1] - 1) - 1;     // 调整纵向链贡献
        ans += pw2[l] * (pw2[r + 1] - 1) - 1;     // 调整横向链贡献
        ans %= P;
    }
    
    // 最终结果：减去所有单个节点的方案（T=1要求至少2个节点）
    cout << (ans - n * m + P) % P;
}

复杂度分析

• 时间复杂度：预处理阶段为$O(N×M)$（$4$ 个方向遍历网格，每个节点处理常数次）；分情况计算阶段也为$O(N×M)$（每个节点仅遍历一次）。整体复杂度为$O(N×M)$，可满足 $N,M≤1000$的数据规模（总操作数约 $10^6$，无超时风险）。
• 空间复杂度：辅助数组 edge、line、quad 均为 $O(N×M)$，dp 数组为$O(N×M)$，pw2 数组为 O(1e6)（可提前预定义）。整体空间复杂度为 $O(N×M)$，在 $1000×1000$网格下约为 $40MB$（每个数组元素为长整$1000×1000×8$ 字节 = $8MB$），完全可接受。