51nod 1486 大大走格子(容斥+dp+组合数)

解题思路

　　暴力容斥复杂度太高，无法接受，考虑用$dp$。设$f(i)$表示从左上角开始不经过前面的阻断点，只经过$i$的阻断点。那么可以考虑容斥，用经过$i$的总方案数减去前面的阻断点到它的方案数，那么转移方程$$f(i)=C(x_i+y_i-2,x_i)-\sum\limits_{j=1}^{i-1}f(j)C(x_i-x_j,y_i-y_j)$$

　　时间复杂度$O(n^2)$

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long LL;

const int N=200005;

const int M=2005;

const int MOD=1e9+7;

inline int rd(){

	int x=0,f=1; char ch=getchar();

	while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();

	while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return f?x:-x;

}

int h,w,n,f[M],fac[N],inv[N];

struct Node{

	int x,y;

	friend bool operator<(const Node A,const Node B){

		return A.x==B.x?A.y<B.y:A.x<B.x;

	}

}node[M];

inline int fast_pow(int x,int y){

	int ret=1;

	for(;y;y>>=1){

		if(y&1) ret=1ll*ret*x%MOD;

		x=1ll*x*x%MOD;

	}

	return ret;

}

inline void prework(){

	fac[0]=1; inv[0]=1;

	for(int i=1;i<=h+w;i++) fac[i]=1ll*fac[i-1]*i%MOD;

	inv[h+w]=fast_pow(fac[h+w],MOD-2);

	for(int i=h+w-1;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%MOD;

}

inline int C(int x,int y){

	if(y<0) return 0;

	return 1ll*fac[x]*inv[y]%MOD*inv[x-y]%MOD;

}

int main(){

	h=rd(),w=rd(),n=rd(); prework();

	for(int i=1;i<=n;i++)

		node[i].x=rd(),node[i].y=rd();

	node[++n].x=h,node[n].y=w;

	sort(node+1,node+1+n); int x,y;

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

		x=node[i].x,y=node[i].y;

		f[i]=C(x-1+y-1,y-1);

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

			(f[i]-=1ll*f[j]*C(x-node[j].x+y-node[j].y,y-node[j].y)%MOD)%=MOD;

		f[i]=(f[i]+MOD)%MOD;

	}

	printf("%d\n",f[n]);

	return 0;

}

巴特西

51nod 1486 大大走格子(容斥+dp+组合数)

解题思路

代码

最新文章

热门文章