首页 > 代码库 > 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 大大走格子
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。