【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;

}