51nod 1486

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1486

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示例

跟前面做过的很类似，但是增加了一些障碍格子，很闹心啊。。。容斥也不太懂，看了dp的作法还挺好懂的把，写的太丑被卡时一早上。。。

我们不妨计算出所有的方案然后减去有障碍格子的方案，令f[i]表示从(1,1)到第i个障碍点的合法路径，也就是说除了i点，路径上得点都合法。

这样的话不难得出方程 f[i]=C(xi+yi-2,xi-1)-Σ_j=1^i-1f[j]*C(xi+yi-xj-yj,xi-xj) ;

这个方程相当于枚举了所有不合法的路径中第一个障碍格子，显然之后的所有路径都至少包含一个障碍格，所以都是非法的，

这个方程前面就是所有的路径方案，后面就是所有的包含障碍的路径方案，减去就是要求的状态了，

显然对于(a,b)-(c,d)格子间所有的路径数我们根据组合数能轻易的得到，打表就好了，注意并不是i之前的所有点都一定能到达i，记得判断一下。

如果把(h,w)看做是一个最后的障碍点的话，ans=f[n+1].

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define LL long long
 4 LL mod=1e9+7;
 5 LL dp[2005];
 6 LL f[200005],inv[200005];
 7 struct node{int x,y;}P[2005];
 8 int read(){
 9     int x=0;char c=getchar();
10     while(!isdigit(c)) c=getchar();
11     while(isdigit(c)) x=x*10+c-'0',c=getchar();
12     return x;
13 }
14 bool cmp(node A,node B)
15 {
16     if(A.x==B.x) return A.y<B.y;
17     return A.x<B.x;
18 }
19 LL qpow(LL a,LL b)
20 {
21     LL r=1;
22     while(b){
23         if(b&1) r=r*a%mod;
24         a=a*a;
25         b>>=1;
26     }
27     return r;
28 }
29 inline LL C(LL N,LL M) {return f[N]*inv[M]%mod*inv[N-M]%mod;}
30 int main()
31 {
32     LL h,w,n,i,j,k;
33     scanf("%lld%lld%lld",&h,&w,&n);
34     for(i=1;i<=n;++i)  P[i].x=read(),P[i].y=read();
35     sort(P+1,P+1+n,cmp);
36     P[n+1].x=h; P[n+1].y=w;
37     inv[0]=f[0]=1;
38     for(i=1;i<=h+w;++i)
39     {
40         f[i]=i*f[i-1]%mod;
41         inv[i]=qpow(f[i],mod-2);
42     }
43     dp[1]=C(P[1].x+P[1].y-2,P[1].x-1);
44     for(i=2;i<=n+1;++i)
45     {
46         LL s=0;
47         for(j=1;j<i;++j)
48         {
49           if(P[j].x<=P[i].x&&P[j].y<=P[i].y)
50           s=(s+dp[j]*C(P[i].x+P[i].y-P[j].x-P[j].y,P[i].x-P[j].x))%mod;
51         }
52         dp[i]=(C(P[i].x+P[i].y-2,P[i].x-1)-s+mod)%mod;
53     }
54     printf("%lld
",dp[n+1]);
55     return 0;
56 }