首页 > 代码库 > 51nod1486 大大走格子

51nod1486 大大走格子

容斥定理+dp。。。妈呀#1rp耗尽了难怪最近那么衰。。。

#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long longint read(){	int x=0;char c=getchar();	while(!isdigit(c)) c=getchar();	while(isdigit(c)) x=x*10+c-‘0‘,c=getchar();	return x;}const int nmax=2e5+5;const int maxn=2e3+5;const int mod=1e9+7;struct node{	int a,b;	bool operator<(const node&rhs)const{	  return a<rhs.a||a==rhs.a&&b<rhs.b;}};node ns[maxn];int h,w,n;ll fac[nmax],inv[nmax],sm[maxn];ll pow(ll a,ll b){	ll ans=a;--b;	while(b){		if(b&1) ans=ans*a%mod;		a=a*a%mod;b>>=1;	}	return ans;}void init(){	fac[0]=1;fac[1]=1;rep(i,2,h+w) fac[i]=fac[i-1]*i%mod;	int t=max(h,w);inv[t]=pow(fac[t],mod-2);inv[0]=1;	dwn(i,t-1,1) inv[i]=inv[i+1]*(i+1)%mod;}int main(){	h=read(),w=read(),n=read();	init();	rep(i,1,n) ns[i].a=read(),ns[i].b=read();	ns[++n].a=h,ns[n].b=w;	sort(ns+1,ns+n+1);	int ta,tb,ca,cb;	rep(i,1,n){		ta=ns[i].a;tb=ns[i].b;		sm[i]=fac[ta+tb-2]*inv[ta-1]%mod*inv[tb-1]%mod;		rep(j,1,i-1) {			if(ns[j].a<=ta&&ns[j].b<=tb){				ca=ta-ns[j].a;cb=tb-ns[j].b;				sm[i]=(sm[i]-fac[ca+cb]*inv[ca]%mod*inv[cb]%mod*sm[j]%mod+mod)%mod;			}		}	}	printf("%lld\n",sm[n]);	return 0;}

  

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 22 22 3
Output示例
2

51nod1486 大大走格子