自动搬运

查看原文

来自洛谷，原作者为

	Egg_eating_master Always break; Never continue; | 我吃了个蛋

搬运于2025-08-24 23:09:38，当前版本为作者最后更新于2025-02-10 21:34:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：两条从 $(1,1)$ 到 $(n,m)$ 的路径除两个端点外不交，并且经过所有 $k$ 个关键点。求方案数。

首先这两条路径一定是一条从 $(2,1)$ 到 $(n,m-1)$，一条从 $(1,2)$ 到 $(n-1,m)$。

考虑不要求两条路径不交怎么做。我们 DP 即可，设 $dp_{i,j}$ （$i>j$）表示考虑了前 $i$ 个关键点，目前一条路径以 $i$ 结尾，另一条以 $j$ 结尾的方案数。转移是平凡的，可以做到 $O(k^2)$。

然后考虑减掉相交的方案数。我们钦定两条路径在第一次相交的位置“互换身份”，那么就变成了一条从 $(2,1)$ 到 $(n-1,m)$ 的路径，和一条从 $(1,2)$ 到 $(n,m-1)$ 的路径。对这个东西计数仍然可以使用上面的 DP。

注意需要特判 $(1,1)$ 或 $(n,m)$ 本身就是关键点的情况。

然后就做完了！

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2010, maxm = 2000005, mod = 1e9 + 7;
int n, m, k;
struct node {
    int x, y;
    bool operator < (const node &a) const {return x + y < a.x + a.y;}
} a[maxn];
int dp[maxn][maxn];
int fac[maxm], ifac[maxm];
int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return res;
}
void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    ifac[n] = power(fac[n], mod - 2);
    for (int i = n - 1; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
int C(int n, int m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
int calc(int p, int q) {return C(a[q].x + a[q].y - a[p].x - a[p].y, a[q].x - a[p].x);}
int solve(int p, int q) {
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
            dp[i][j] = 0;
    dp[p][q] = 1;
    for (int i = 3; i <= k; i++) {
        for (int j = 1; j <= i - 2; j++) {
            dp[i - 1][i] = (dp[i - 1][i] + dp[i - 1][j] * calc(j, i)) % mod;
            dp[i][j] = (dp[i][j] + dp[i - 1][j] * calc(i - 1, i)) % mod;
            dp[i][i - 1] = (dp[i][i - 1] + dp[j][i - 1] * calc(j, i)) % mod;
            dp[j][i] = (dp[j][i] + dp[j][i - 1] * calc(i - 1, i)) % mod;
        }
    }
    return dp[k - 1][k];
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k; init(n + m);
    a[1] = (node){2, 1}, a[2] = (node){1, 2};
    for (int i = 3; i <= k + 2; i++) {
        cin >> a[i].x >> a[i].y;
        if (a[i].x == 1 && a[i].y == 1) i--, k--;
        if (a[i].x == n && a[i].y == m) i--, k--;
    }
    a[k + 3] = (node){n, m - 1}, a[k + 4] = (node){n - 1, m};
    sort(a + 3, a + k + 3);
    k += 4;
    cout << (solve(1, 2) - solve(2, 1) + mod + mod) * 2 % mod << '\n';
    return 0;
}