题解：P11704 [ROIR 2025] 旅行路线

· · 题解

P11704 ROIR 2025 旅行路线

给定 k 个关键点，要求选出两条从 (1,1) 到 (n,m) 的路径，要求这两条路径覆盖所有关键点，且除起点和终点外，两条路径不相交。

n,m\le 10^6,k\le 5000

先来考虑如何解决，两条路径不交的限制。

两条路径不交，那我们一定可以推出第一步一定是分别走到 (1,2) 和 (2,1)，同理，最后一步一定是分别从 (n,m-1) 和 (n-1,m) 走到 (n,m) ，我们对这 4 个点进行考虑。

要求路径不交那合法情况一定是从 (2,1) 走到 (n,m-1) ，从 (1,2) 走到 (n-1,m) 的两条路径。考虑减去相交的情况，我们发现对于每一条相交的路径都可以钦定它在第一次相交的位置交换路径，那一定对应一组从 (2,1) 走到 (n-1,m) ，(1,2) 走到 (n,m-1) 的路径，也就是说它们构成双射关系，我们直接计算后面的方案即可。

接下来考虑如何满足覆盖所有关键点。我们逐个关键点进行钦定，考虑 dp 。

首先我们转移过程一定是逐条考虑从左上到右下的每一条对角线，按照 x+y 从小到大排序即可。

设f_{a,b} 表示第一条路径走到了第 a 个关键点，第二条路径走到了第 b 个关键点，转移分为三种，

  1. 钦定第一条路径走到了 i
  2. 钦定第二条路径走到了 i

转移系数即为从一个点走到另一个的方案，但是不难发现直接转移我们会计算重复两个点都经过点 i 的方案。

但是在这题中其实我们没有必要考虑这种情况，两个点经过点 i 也就意味这两条路一定相交，而从一开始我们就要除去这种情况，所以我们没有必要把它的系数算对，只要确保前后可以做差消去即可。

如果我们真的要正确计算它的系数该怎么办呢。

一种方式是考虑把两个点都经过 i 的的单独拎出来，并且把转移系数换为从一个点到另一个点不经过其他关键点的方案数。这样可以做到不算重，但计算系数本人只能做到 k^3 不能通过本题，不再详细介绍。

还有一种可以做到 O(k^2) 的容斥做法。我们把一组路径拎出来看，假设中间有 k 个重合的关键点，那我们有一个最直接的容斥方法，钦定路径上重合点的集合 S ，答案即为 \sum_{S}(-1)^{|S|}Ans(S) ，我们可以把这个容斥系数直接放到 dp 转移中，相当于每钦定一个重合关键点乘一个 -1 的系数即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e3+10,M=2e6+10,mod=1e9+7;
int n,m,k,op;
struct nod{int x,y;}s[N];
bool cmp(nod x,nod y){return x.x+x.y<y.x+y.y;}
int dp[N][N],fac[M],inv[M];
int Pow(int a,int k){
    int ans=1;
    while(k){
        if(k&1)ans=ans*a%mod;
        k>>=1;a=a*a%mod;
    }
    return ans;
}
int C(int n,int m){
    if(n<m||m<0)return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int trans(int i,int j){return C(s[j].x-s[i].x+s[j].y-s[i].y,s[j].x-s[i].x);}
int d[N][N];
int slove(int I,int J){
    for(int i=1;i<=k+4;i++)for(int j=1;j<=k+4;j++)dp[i][j]=0;
    dp[I][J]=1; 
    for(int i=3;i<=k+4;i++){
        for(int j=1;j<i-1;j++){
            dp[i-1][i]+=dp[i-1][j]*trans(j,i)%mod;dp[i-1][i]%=mod;
            dp[i][j]+=dp[i-1][j]*trans(i-1,i)%mod;dp[i][j]%=mod;
            dp[i][i-1]+=dp[j][i-1]*trans(j,i)%mod;dp[i][i-1]%=mod;
            dp[j][i]+=dp[j][i-1]*trans(i-1,i)%mod;dp[j][i]%=mod;
            dp[i][i]-=(dp[i-1][j]+dp[j][i-1])%mod*trans(j,i)%mod*trans(i-1,i)%mod;dp[i][i]%=mod;
        }
        dp[i][i-1]+=dp[i-1][i-1]*trans(i-1,i)%mod;dp[i][i-1]%=mod;
        dp[i-1][i]+=dp[i-1][i-1]*trans(i-1,i)%mod;dp[i-1][i]%=mod;
        dp[i][i]-=dp[i-1][i-1]*trans(i-1,i)%mod*trans(i-1,i)%mod;dp[i][i]%=mod;
    }
    return (dp[k+3][k+4]+mod)%mod;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>n>>m>>k;
    for(int i=3;i<=k+2;i++){
        cin>>s[i].x>>s[i].y;
        if(s[i].x==1&&s[i].y==1)i--,k--;
        if(s[i].x==n&&s[i].y==m)i--,k--;
    }
    fac[0]=1;for(int i=1;i<=n+m;i++)fac[i]=fac[i-1]*i%mod;
    inv[n+m]=Pow(fac[n+m],mod-2);for(int i=n+m-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
    sort(s+3,s+3+k,cmp);
    s[1]=nod{1,2};s[2]=nod{2,1};
    s[k+3]=nod{n-1,m};s[k+4]=nod{n,m-1};
    int ans=slove(1,2)-slove(2,1);
    cout<<(ans+mod)%mod*2%mod<<"\n";
    return 0;
}