题解

问题分析

题目要求计算从 $(1,1)$ 到 $(n,m)$ 再返回 $(1,1)$ 的回路数量，满足：

1. 总步数恰好为 $2n + 2m - 4$
2. 每个格子最多访问一次
3. 必须经过所有 $k$ 个景点

关键观察

1. 路径结构：由于步数限制和不能重复访问，实际上路径是两条不相交的路径：

   • 一条从 $(1,1)$ 到 $(n,m)$
   • 一条从 $(n,m)$ 返回 $(1,1)$
   • 这两条路径合起来覆盖所有景点

2. 组合数学：在网格图中，从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的路径数为：

   $$C((x_2-x_1)+(y_2-y_1), (x_2-x_1))$$

3. 容斥原理：需要处理两条路径不相交的条件，使用 Lindström–Gessel–Viennot 引理

算法思路

Lindström–Gessel–Viennot 引理应用：

1. 问题转化：将回路分解为两条路径：

   • 路径1：$(1,2) \to (n-1,m)$
   • 路径2：$(2,1) \to (n,m-1)$
   • 这样确保两条路径不相交

2. 状态设计：

   • dp[i][j][b] 表示处理到第 $i$ 个点，上一条路径终点在 $j$，奇偶性为 $b$ 的方案数
   • 通过容斥排除相交的路径

3. 转移方程：

   • 延续当前路径：dp[i+1][j][b] += dp[i][j][b] * comb(a[i], a[i+1])
   • 交换路径：dp[i+1][i][b^1] += dp[i][j][b] * comb(a[j], a[i+1])
   • 容斥修正：减去相交情况的重复计数

核心函数

comb(a, b)

计算从点 $a$ 到点 $b$ 的路径数：

int comb(const pii &a, const pii &b) {
    if(a.first > b.first || a.second > b.second) 
        return 0;
    return C(b.second - a.second + b.first - a.first, 
             b.second - a.second);
}

动态规划转移

dp[i+1][j][b] = (dp[i+1][j][b] + v * comb(a[i], a[i+1])) % p;
dp[i+1][i][b^1] = (dp[i+1][i][b^1] + v * comb(a[j], a[i+1])) % p;
dp[i+1][i+1][1] = (dp[i+1][i+1][1] - v * comb(a[i], a[i+1]) * comb(a[j], a[i+1]) % p + p) % p;

算法步骤

1. 预处理：计算组合数 $C_n^m \bmod 10^9+7$
2. 输入处理：将所有景点按坐标和排序
3. 第一次DP：计算包含 $(1,1)$ 和 $(n,m)$ 的路径方案
4. 第二次DP：计算修正后的路径方案（交换起点）
5. 容斥计算：用两次DP结果相减得到最终答案
6. 输出：结果乘以2（两条路径对称）

复杂度分析

• 预处理：$O(N)$，$N = 3\times 10^6$
• 动态规划：$O(k^3)$，但 $k \leq 2000$ 实际可接受
• 总复杂度：$O(N + k^3)$

算法标签

• 组合数学
• 动态规划
• 容斥原理
• Lindström–Gessel–Viennot 引理
• 不相交路径计数
• 网格图路径