旅行路線：

很有參考價(jià)值的一道題，其他題解有點(diǎn)抽象，我來。

轉(zhuǎn)化題意

題意轉(zhuǎn)化為 \((1,2)→(n-1,m),(2,1)→(n,m-1)\) 的兩條鏈不相交且經(jīng)過所有關(guān)鍵點(diǎn)的方案數(shù)。

其他點(diǎn)沒用，我們以下的點(diǎn)指關(guān)鍵點(diǎn)。

無不能相交限制的 DP

由于 \(x_i\le x_j,y_i\le y_j\)，\(i\) 才可以轉(zhuǎn)移到 \(j\)。所以按 \((x_i+y_i)\) 排序就可以遞推了，當(dāng)然你可以建 DAG 把拓?fù)湫蚺芟聛硪惨粯拥摹?/p>

然后 \(f_{i,j}\) 表示前 \(i\) 個(gè)點(diǎn)都被經(jīng)過了，然后第二條鏈末尾為 \(j(j\le i)\)，同時(shí)這個(gè)含義順便欽定了第一條鏈的末尾為 \(i\)。這個(gè)含義舒服多了，顯然是從 \(f_i → f_{i+1}\) 的轉(zhuǎn)移形式。

但是你顯然不能讓 \(2\) 鏈低 \(1\) 鏈一等，正確的路徑應(yīng)該同時(shí)轉(zhuǎn)移（額外條件我們用容斥解決，在此先考慮 DP），把含義變成：第一條鏈末尾為 \(i\)，第二條鏈末尾為 \(j\)，前 \(\max(i,j)\) 的點(diǎn)都被經(jīng)過了。
那么轉(zhuǎn)移的下一步一定是 \(\max(i,j)+1\) 這個(gè)點(diǎn)，這樣 \(1\) 鏈 \(2\) 鏈就同等了！

由于是 DP，所以我們必須對 DP 含義負(fù)責(zé)，轉(zhuǎn)移時(shí)，我們不好欽定在轉(zhuǎn)移過程種兩條鏈沒有相交（如果欽定路徑種不交有 \(O(k^3)\) 做法，容斥加組合數(shù)預(yù)處理一個(gè) \(dis2\) 數(shù)組，我有個(gè)極好的處理辦法，可惜這里地方太小，我寫不下），那么我們直接欽定轉(zhuǎn)移路徑上的重合點(diǎn)個(gè)數(shù)二項(xiàng)式反演。
\(f(i)\)：欽定了 \(i\) 個(gè)點(diǎn)重合的方案數(shù)。
\(g(i)\)：恰好 \(i\) 個(gè)點(diǎn)重合的方案數(shù)。
我們用 \(g(0)\) 轉(zhuǎn)移，\(g(0)=\sum_i (-1)^i f(i)\)，發(fā)現(xiàn) \(i\) 與 \(f(i)\) 的次冪一樣，所以把 \(-1\) 下發(fā)給轉(zhuǎn)移到重合點(diǎn)的時(shí)候，這樣我們就不用考慮轉(zhuǎn)移的時(shí)候鏈相交的問題了。

這個(gè)東西很抽象啊！因?yàn)檫@時(shí)我們已經(jīng)不保證 DP 的含義了。

因?yàn)槲覀?\(f_{i,i}\) 的值終究要貢獻(xiàn)給最后的答案，而我們真正的 \(f_{i,i}\) 早在欽定的點(diǎn)個(gè)數(shù)更小的時(shí)候計(jì)算了，所以可以這么亂來。對不起了，DP……我沒有對你的含義負(fù)責(zé)。

直接轉(zhuǎn)移就行了，我的代碼很帥，大家隨便看。

相交限制的處理

\((1,2)→(n-1,m),(2,1)→(n,m-1)\) 相交如何計(jì)算？
我們可以畫一下相交的情況，然后在第一次相交的時(shí)候交換鏈 \(1\) 和 \(2\) 的路徑（感覺這個(gè)做法很像反射容斥）。
發(fā)現(xiàn)相交路徑與 \((1,2)→(n,m-1),(2,1)→(n-1,m)\) 雙射。
\(ans=總路徑數(shù) - 相交路徑數(shù)\)。
兩者只是起點(diǎn)終點(diǎn)不一樣。

很帥的代碼

\(O(k^2)\)，感覺代碼很可讀所以一些地方不說了。

#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;
}

刷表無敵好看！！！

一些閑話

為什么你代碼這么長？

因?yàn)檫@題涉及到相減的情況，并且我們轉(zhuǎn)移時(shí)的重合在兩個(gè) DP 里都會被統(tǒng)計(jì)到，最終兩者相減終為 \(0\)，所以在轉(zhuǎn)移上折騰了這么久，終究沒啥用啊……但是這個(gè)更符合直覺吧。

如何 \(O(k^3)\)？

哈哈哈，我沒有丟下你們。

\(dis2_{i,j}\)：從 \(i\) 到 \(j\) 中途不經(jīng)過別的點(diǎn)的路徑條數(shù)。

先用全部的方案減去不合法的方案，不合法的方案我們枚舉轉(zhuǎn)移路徑中第一個(gè)重合點(diǎn)。（這里假設(shè)按 \(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}\)

那么相當(dāng)于上面不用二項(xiàng)式反演，也就是不用 \(-1\) 的系數(shù)，直接把上面的 \(dis\) 改成 \(dis2\) 就好了。