1486 大大走格子
题目来源： CodeForces
基准时间限制：1 秒 空间限制：131072 KB 分值: 160 难度：6级算法题
收藏
关注
有一个h行w列的棋盘，里面有一些格子是不能走的，现在要求从左上角走到右下角的方案数。
Input
单组测试数据。
第一行有三个整数h, w, n(1 ≤ h, w ≤ 10^5, 1 ≤ n ≤ 2000)，表示棋盘的行和列，还有不能走的格子的数目。
接下来n行描述格子，第i行有两个整数ri, ci (1 ≤ ri ≤ h, 1 ≤ ci ≤ w)，表示格子所在的行和列。
输入保证起点和终点不会有不能走的格子。
Output
输出答案对1000000007取余的结果。
Input示例
3 4 2
2 2
2 3
Output示例
2
#include<bits/stdc++.h>
#define P 1000000007
using namespace std;
typedef long long ll;
int h,w,n;
struct node
{
int row;
int col;
bool operator<(node n2)
{
if(n2.row!=row)return row<n2.row;
else return col<n2.col;
}
} Nod[2010];
int fac[200005],inv[200005];
inline void Pre(int n){
int i;
for(fac[0]=1,i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%P;
for(inv[0]=inv[1]=1,i=2;i<=n;++i) inv[i]=1ll*(P-P/i)*inv[P%i]%P;
for(i=1;i<=n;++i) inv[i]=1ll*inv[i]*inv[i-1]%P;
}
inline int C(int x,int y){return 1ll*fac[x]*inv[y]%P*inv[x-y]%P;}
ll num(int i,int j)//点i到j的方案数
{
return C(Nod[j].col-Nod[i].col+Nod[j].row-Nod[i].row,Nod[j].col-Nod[i].col);
}
int t[2005];
int main()
{
//freopen("in.txt","r",stdin);
cin>>h>>w>>n;
Pre(h+w);
for(int i=1;i<=n;i++)cin>>Nod[i].row>>Nod[i].col;
Nod[n+1].row=h;Nod[n+1].col=w;
Nod[0].row=1;Nod[0].col=1;
sort(Nod,Nod+n+1);
ll p=P;
for(int i=1;i<=n+1;i++)
{
t[i]=num(0,i);
for(int j=1;j<i;j++)
{
if(Nod[j].col<=Nod[i].col)
t[i]=(1ll*t[i]-t[j]*num(j,i)%P+P)%P;
}
}
ll ans=1ll*t[n+1];
cout<<ans<<endl;
}