题解：P11704 [ROIR 2025] 旅行路线
a1a2a3a4a5
·
·
题解
很有参考价值的一道题，其他题解有点抽象，我来。
转化题意
题意转化为 (1,2)→(n-1,m),(2,1)→(n,m-1) 的两条链不相交且经过所有关键点的方案数。
其他点没用，我们以下的点指关键点。
无不能相交限制的 DP
由于 x_i\le x_j,y_i\le y_j，i 才可以转移到 j。所以按 (x_i+y_i) 排序就可以递推了，当然你可以建 DAG 把拓扑序跑下来也一样的。
然后 f_{i,j} 表示前 i 个点都被经过了，然后第二条链末尾为 j(j\le i)，同时这个含义顺便钦定了第一条链的末尾为 i。这个含义舒服多了，显然是从 f_i → f_{i+1} 的转移形式。
但是你显然不能让 2 链低 1 链一等，正确的路径应该同时转移（额外条件我们用容斥解决，在此先考虑 DP），把含义变成：第一条链末尾为 i，第二条链末尾为 j，前 \max(i,j) 的点都被经过了。
那么转移的下一步一定是 \max(i,j)+1 这个点，这样 1 链 2 链就同等了！
由于是 DP，所以我们必须对 DP 含义负责，转移时，我们不好钦定在转移过程种两条链没有相交（如果钦定路径种不交有 O(k^3) 做法，容斥加组合数预处理一个 dis2 数组，我有个极好的处理办法，可惜这里地方太小，我写不下），那么我们直接钦定转移路径上的重合点个数二项式反演。
$g(i)$：恰好 $i$ 个点重合的方案数。
我们用 $g(0)$ 转移，$g(0)=\sum_i (-1)^i f(i)$，发现 $i$ 与 $f(i)$ 的次幂一样，所以把 $-1$ 下发给转移到重合点的时候，这样我们就不用考虑转移的时候链相交的问题了。
这个东西很抽象啊！因为这时我们已经不保证 DP 的含义了。
因为我们 $f_{i,i}$ 的值终究要贡献给最后的答案，而我们真正的 $f_{i,i}$ 早在钦定的点个数更小的时候计算了，所以可以这么乱来。对不起了，DP……我没有对你的含义负责。
直接转移就行了，我的代码很帅，大家随便看。
## 相交限制的处理
$(1,2)→(n-1,m),(2,1)→(n,m-1)$ 相交如何计算？
我们可以画一下相交的情况，然后在第一次相交的时候交换链 $1$ 和 $2$ 的路径（感觉这个做法很像反射容斥）。
发现相交路径与 $(1,2)→(n,m-1),(2,1)→(n-1,m)$ 双射。
$ans=总路径数 - 相交路径数$。
两者只是起点终点不一样。
## 很帅的代码
$O(k^2)$，感觉代码很可读所以一些地方不说了。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int QAQ=2010000,ovo=5100;
const ll mo=1e9+7;
int n,m,k,cnt,jc[QAQ];
struct xxx {int x,y;} d[ovo];
bool cmp(xxx a,xxx b) {return a.x+a.y<b.x+b.y;}
int ksm(ll x,int k)
{
ll da=1;
for(;k;k>>=1,x=x*x%mo) if(k&1) da=da*x%mo;
return da;
}
int cnm(int n,int m) {return (ll)jc[n]*ksm((ll)jc[m]*jc[n-m]%mo,mo-2)%mo;}
int roxy(int i,int j)
{
if(d[i].x<=d[j].x&&d[i].y<=d[j].y)
return cnm(d[j].y-d[i].y+d[j].x-d[i].x,d[j].y-d[i].y);
return 0;
}
#define jia(x,y) x=(x+y)%mo
#define jian(x,y) x=(x-(y))%mo
int dis[ovo][ovo],ans;
ll f[ovo][ovo];
int chuli(int i,int j)
{
for(int i=1;i<=cnt;i++) for(int j=1;j<=cnt;j++) f[i][j]=0;
f[i][j]=1;
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
{
if(i>j)
jia(f[i+1][j],f[i][j]*dis[i][i+1]),
jia(f[i][i+1],f[i][j]*dis[j][i+1]),
jian(f[i+1][i+1],f[i][j]*dis[i][i+1]%mo*dis[j][i+1]);
else if(i<j)
jia(f[i][j+1],f[i][j]*dis[j][j+1]),
jia(f[j+1][j],f[i][j]*dis[i][j+1]),
jian(f[j+1][j+1],f[i][j]*dis[i][j+1]%mo*dis[j][j+1]);
else
jia(f[i+1][i],f[i][i]*dis[i][i+1]),
jia(f[i][i+1],f[i][i]*dis[i][i+1]),
jian(f[i+1][i+1],f[i][i]*dis[i][i+1]%mo*dis[i][i+1]);
}
return f[cnt-1][cnt];
}
signed main()
{
jc[0]=1;
for(int i=1;i<=2000000;i++) jc[i]=(ll)jc[i-1]*i%mo;
cin>>n>>m>>k;
d[++cnt]={1,2},d[++cnt]={2,1};
for(int i=1,x,y;i<=k;i++)
{
cin>>x>>y;
if(x==1&&y==1) continue;
if(x==n&&y==m) continue;
d[++cnt]={x,y};
}
d[++cnt]={n-1,m},d[++cnt]={n,m-1};
sort(d+3,d+cnt-2+1,cmp);
for(int i=1;i<=cnt;i++) for(int j=i;j<=cnt;j++) dis[i][j]=roxy(i,j);
cout<<((chuli(1,2)-chuli(2,1))%mo+mo)%mo*2%mo;
return 0;
}
```
刷表无敌好看！！！
## 一些闲话
### 为什么你代码这么长？
因为这题涉及到相减的情况，并且我们转移时的重合在两个 DP 里都会被统计到，最终两者相减终为 $0$，所以在转移上折腾了这么久，终究没啥用啊……但是这个更符合直觉吧。
### 如何 $O(k^3)$？
哈哈哈，我没有丢下你们。
$dis2_{i,j}$：从 $i$ 到 $j$ 中途不经过别的点的路径条数。
先用全部的方案减去不合法的方案，不合法的方案我们枚举转移路径中第一个重合点。（这里假设按 $x_i+y_i$ 排完序了）
$dis2_{i,j}=\binom{y_j-y_i+x_j-x_i}{x_j-x_i}-\sum_{i<k<j} dis2_{i,k}\binom{y_j-y_k+x_j-x_k}{x_j-x_k}
那么相当于上面不用二项式反演，也就是不用 -1 的系数，直接把上面的 dis 改成 dis2 就好了。