首页 > 代码库 > 【bzoj4676】 两双手

【bzoj4676】 两双手

http://www.lydsy.com/JudgeOnline/problem.php?id=4767 (题目链接)

题意

  求在网格图上从$(0,0)$走到$(n,m)$,其中不经过一些点的路径方案数。

Solution

  转换一下就变成了题意中的模型。我们将网格上的起点和不允许经过的点全部看做一类点,用$f[i]$表示从第$i$个点不经过其它点到达终点的路径条数,用$D(i,j)$表示个点之间的路径条数,$T$表示终点。转移:

\begin{aligned}  f[i]=D(i,T)-\sum_j D(i,j)*f[j]   \end{aligned}

  其中$j$在$i$的右上方。然后注意特判一下问题无法转换的情况。

细节

  预处理别预处理少了?

代码

// bzoj4767#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf (1ll<<30)#define MOD 1000000007#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)using namespace std;const int maxn=1000;int Ex,Ey,Ax,Ay,Bx,By,na,nb,n,m;LL fac[maxn*maxn],ifac[maxn*maxn],f[maxn];struct point {	int x,y;	friend bool operator <= (point a,point b) {return a.x<=b.x && a.y<=b.y;}}p[maxn];LL power(LL a,LL b) {	LL res=1;	while (b) {		if (b&1) (res*=a)%=MOD;		b>>=1;(a*=a)%=MOD;	}	return res;}LL C(int n,int m) {	return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;}bool cmp(point a,point b) {	return a.x==b.x ? a.y<b.y : a.x<b.x;}LL D(point a,point b) {	return C(b.x+b.y-a.x-a.y,b.x-a.x);}int main() {	scanf("%d%d%d",&Ex,&Ey,&n);	scanf("%d%d%d%d",&Ax,&Ay,&Bx,&By);	if ((Ex*By-Ey*Bx)%(Ax*By-Ay*Bx)) {puts("0");return 0;}	na=(Ex*By-Ey*Bx)/(Ax*By-Ay*Bx);	nb=Bx ? (Ex-Ax*na)/Bx : (Ey-Ay*nb)/By;	if (p[0].x<0 || p[0].y<0) {puts("0");return 0;}	for (int ca,cb,x,y,i=1;i<=n;i++) {		scanf("%d%d",&x,&y);		if ((x*By-y*Bx)%(Ax*By-Ay*Bx)) continue;		ca=(x*By-y*Bx)/(Ax*By-Ay*Bx);		cb=Bx ? (x-Ax*ca)/Bx : (y-Ay*ca)/By;		if (0<=ca && ca<=na && 0<=cb && cb<=nb) p[++m]=(point){ca,cb};	}	sort(p+1,p+1+m,cmp);	n=na+nb;	p[m+1]=(point){na,nb};p[0]=(point){0,0};	fac[0]=1;for (int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD;	ifac[n]=power(fac[n],MOD-2);	for (int i=n;i>=1;i--) ifac[i-1]=ifac[i]*i%MOD;	for (int i=m;i>=0;i--) {		f[i]=D(p[i],p[m+1]);		for (int j=i+1;j<=m;j++) 			if (p[i]<=p[j]) (f[i]+=MOD-D(p[i],p[j])*f[j]%MOD)%=MOD;	}	printf("%lld",f[0]);	return 0;}

 

【bzoj4676】 两双手