文章目录

题目链接：

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1486&judgeId=563640
参考博客：https://blog.csdn.net/mrazer/article/details/52047436
注意阶乘要预处理到2e5，因为计算的时候是行+列
普通 n n n 行 m m m 列没有不能走的方案数就是 C ( n + m − 2 , n − 1 ) C(n+m-2,n-1) C(n+m−2,n−1) 种
假如不能走的点叫做黑点
现在记一个 d p [ i ] dp[i] dp[i] 为考虑了不走这个黑点的左上角那些黑点，走到第 i 个黑点的方案数

d p [ i ] dp[i] dp[i] 就是不经过黑点的方案数 减去 所有经过一次左上角的某个黑点的然后到这个点的方案数

但是，为啥只减去经过一次的喃？因为经过的这一次其实也是经过了容斥过后最后的结果，感觉这种容斥好难理解啊

哦，我感觉不像是普通容斥那种
只要经过黑点一次，那就是不合法的，所以感觉是分阶段来求合法的，然后把不合法的剔除，而不合法是走一步就不合法，所以只用枚举前面哪一步不合法，把他减去，那剩下的就是走到这步合法的方案数了

#include"bits/stdc++.h"
#define C(n,m) (m>n?0:(long long)fac[(n)]*invf[(m)]%MOD*invf[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=2e5+5;
const int MOD=1e9+7;
LL dp[maxn];
LL ksm(LL a,LL b,LL mod)
{
	LL res=1,base=a;
	while(b)
	{
		if(b&1)res=(res*base)%mod;
		base=(base*base)%mod;
		b>>=1;
	}
	return res;
}

LL fac[maxn]= {1,1},invf[maxn]= {1,1};
void InitFac(int n)
{
	for(int i=2; i<=n; i++)fac[i]=fac[i-1]*i%MOD;
	invf[n]=ksm(fac[n],MOD-2,MOD);
	for(int i=n-1; i>=2; i--)invf[i]= invf[i+1]*(i+1)%MOD;
}
pair<int,int>a[maxn];
int main()
{
	InitFac(maxn-5);
	int N,M,K;
	while(cin>>N>>M>>K)
	{
		for(int i=1; i<=K; i++)cin>>a[i].first>>a[i].second;
		sort(a+1,a+1+K);
		a[++K]=make_pair(N,M);
		for(int i=1; i<=K; i++)
		{
			int x=a[i].first,y=a[i].second;
			dp[i]=C(x+y-2,x-1);//这个是从起点走到这个黑点的方案数 
			for(int j=1; j<i; j++)
			{
				int xx=a[j].first,yy=a[j].second;
				if(xx>x||yy>y)continue;//不在这个黑点的左上的点不算 
				dp[i]-=dp[j]*C(x-xx+y-yy,x-xx);//减去经过一次这个点左上的黑点的方案数 
				dp[i]=(dp[i]%MOD+MOD)%MOD;
			}
		}
		cout<<dp[K]<<endl;
	}
}