首页 > 代码库 > [51nod1486]大大走格子
[51nod1486]大大走格子
有一个h行w列的棋盘，里面有一些格子是不能走的，现在要求从左上角(1,1)走到右下角(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取余的结果。
组合数学。设ans[i]表示从(1,1)走到第i个不能走的格子，且中间不经过其他障碍格的方案数。（把(h,w)也当成障碍格）
ans[i]= C( X[i]-1+Y[i]-1 , X[i]-1 ) - sum{ ans[j]*C( X[i]-X[j]+Y[i]-Y[j] , X[i]-X[j] ) }，点j在点i的左上方（包括左方或上方）。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define ll long long 7 #define ull unsigned long long 8 #define ui usigned int 9 #define d double10 #define ld long double11 const int maxn=2023,modd=1000000007;12 struct zs{int x,y;}a[maxn];13 int jc[200233],ny[200233],ans[maxn];14 int i,j,k,n,m;15 16 int ra,fh;char rx;17 inline int read(){18 rx=getchar(),ra=0,fh=1;19 while(rx<‘0‘&&rx!=‘-‘)rx=getchar();20 if(rx==‘-‘)fh=-1,rx=getchar();21 while(rx>=‘0‘)ra=ra*10+rx-48,rx=getchar();return ra*fh;22 }23 24 inline int getc(int n,int m){25 return 1ll*jc[n]*ny[n-m]%modd*ny[m]%modd;26 }27 inline int get(int x,int y){28 return getc(x+y,y);29 }30 inline int poi(int a,int b){31 int c=1;32 while(b){33 if(b&1)c=1ll*c*a%modd;34 a=1ll*a*a%modd,b>>=1;35 }return c;36 }37 bool operator <(zs a,zs b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}38 inline void UPD(int &x){if(x<0)x+=modd;}39 int main(){40 n=read(),m=read();int num=read();register int i,j;41 for(i=jc[0]=ny[0]=1;i<=n+m;i++)jc[i]=1ll*jc[i-1]*i%modd,ny[i]=poi(jc[i],modd-2);42 // for(i=1;i<=n||i<=m;i++)for(j=1;j<=i;j++)printf("%d %d c:%d\n",i,j,getc(i,j));43 for(i=1;i<=num;i++)a[i].x=read()-1,a[i].y=read()-1;44 a[++num]=(zs){n-1,m-1};45 std::sort(a+1,a+1+num);46 for(i=1;i<=num;i++){47 ans[i]=get(a[i].x,a[i].y);//printf("(%d,%d) %d\n",a[i].x,a[i].y,ans[i]);48 for(j=1;j<i;j++)if(a[j].y<=a[i].y)49 UPD(ans[i]-=1ll*ans[j]*get(a[i].x-a[j].x,a[i].y-a[j].y)%modd);50 }51 printf("%d\n",ans[num]);52 }
[51nod1486]大大走格子
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。