这场CF又掉分了。。。
这题题意大概就给一个h*w的棋盘，中间有一些黑格子不能走，问只能向右或者向下走的情况下，从左上到右下有多少种方案。
开个sum数组，sum[i]表示走到第i个黑点但是不经过其他黑点的方案数。
式子是sum[i]=c(x[i]+y[i],x[i])-Σ(sum[j]*c(x[i]-x[j]+y[i]-y[j],x[i]-x[j]))。
c(x+y,x)表示从格子(1,1)到(x,y)的方案数（没有黑点)。
因此每个点按x[i]+y[i]的值排个序，然后n^2弄一下他们的拓扑关系，就可以推了。
代码
1 #include<cstdio> 2 #include<algorithm> 3 #include<map> 4 #include<cstring> 5 #include<vector> 6 #include<cmath> 7 #include<iostream> 8 #include<string> 9 #define N 600010 10 #define M 1010 11 #define P 1000000007 12 using namespace std; 13 struct Q{ 14 int x,y,z; 15 }a[N]; 16 int h,w,n,i,j; 17 long long g[N],sum[N]; 18 int exgcd(int a,int b,long long &x,long long &y) 19 { 20 long long t; 21 if (b==0) 22 { 23 x=1;y=0;return a; 24 } 25 exgcd(b,a%b,x,y); 26 t=x; 27 x=y; 28 y=t-a/b*y; 29 } 30 long long cl(int x,int y) 31 { 32 long long a,b,z,zz; 33 z=x+y-2; 34 zz=g[x-1]*g[z-x+1]%P; 35 z=g[z]; 36 exgcd(zz,P,a,b); 37 z=(z*a%P+P)%P; 38 return z; 39 } 40 bool cmp(Q a,Q b) 41 { 42 return a.z<b.z; 43 } 44 int main() 45 { 46 scanf("%d%d%d",&h,&w,&n); 47 g[0]=1; 48 for (i=1;i<=200000;i++) 49 g[i]=(g[i-1]*i)%P; 50 for (i=1;i<=n;i++) 51 { 52 scanf("%d%d",&a[i].x,&a[i].y); 53 a[i].z=a[i].x+a[i].y; 54 } 55 a[n+1].x=h;a[n+1].y=w;a[n+1].z=h+w; 56 sort(a+1,a+1+n+1,cmp); 57 for (i=1;i<=n+1;i++) 58 { 59 sum[i]=cl(a[i].x,a[i].y); 60 for (j=1;j<i;j++) 61 if ((a[j].x<=a[i].x)&&(a[j].y<=a[i].y)) 62 sum[i]=(sum[i]-sum[j]*cl(a[i].x-a[j].x+1,a[i].y-a[j].y+1))%P; 63 } 64 sum[n+1]=(sum[n+1]%P+P)%P; 65 printf("%I64d ",sum[n+1]); 66 }