codeforces #313 div1 C

同BZOJ 3782 上学路线

QAQ 还比那个简单一点

把坐标(1,1)-(n,m)平移成(0,0)-(n-1,m-1)

设dp[i]表示从(1,1)出发第一次经过障碍且到达第i个障碍的方案数

首先到达第i个障碍的方案数为C(x+y,x)

之后我们考虑i是第一个经过的障碍的方案数=到达i的方案数-i不是第一个经过的障碍的方案数

这也是很好算的

容斥一下即可

#include<cstdio>

#include<cstring>

#include<iostream>

#include<cstdlib>

#include<algorithm>

using namespace std;

typedef long long LL;

const int maxn=100010;

const int mod=1e9+7;

int n,m,k,lim;

struct blo{

	int x,y;

}c[2010];

bool cmp(const blo &A,const blo &B){

	if(A.x==B.x)return A.y<B.y;

	return A.x<B.x;

}

LL fac[maxn<<1];

LL inv[maxn<<1];

LL pow_mod(LL v,int p){

	LL tmp=1;

	while(p){

		if(p&1)tmp=tmp*v%mod;

		v=v*v%mod;p>>=1;

	}return tmp;

}

LL C(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;}

LL dp[2010];

void Get_DP(){

	for(int i=1;i<=k;++i){

		dp[i]=C(c[i].x+c[i].y,c[i].x);

		for(int j=1;j<i;++j){

			if(c[j].x<=c[i].x&&c[j].y<=c[i].y){

				dp[i]=dp[i]-dp[j]*C(c[i].x+c[i].y-c[j].x-c[j].y,c[i].x-c[j].x)%mod;

				if(dp[i]<0)dp[i]+=mod;

			}

		}

	}printf("%I64d\n",dp[k]);

}

int main(){

	scanf("%d%d%d",&n,&m,&k);lim=n+m-2;

	for(int i=1;i<=k;++i){

		scanf("%d%d",&c[i].x,&c[i].y);

		c[i].x--;c[i].y--;

	}

	fac[0]=1;k++;c[k].x=n-1;c[k].y=m-1;

	for(int i=1;i<=lim;++i)fac[i]=fac[i-1]*i%mod;

	inv[lim]=pow_mod(fac[lim],mod-2);

	for(int i=lim-1;i>=0;--i)inv[i]=inv[i+1]*(i+1)%mod;

	sort(c+1,c+k+1,cmp);Get_DP();

	return 0;

}