容斥定理+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 long
int 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;
}
收藏
关注有一个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示例
2