bzoj 4767 两双手

Posted on | Views:

容斥 +$dp$ .

  • 把两种移动方式看做两个向量 $\vec a,\vec b$ .因为题目保证它们不共线,所以每个点都可以被写成 $x\cdot \vec a+y\cdot \vec b$ .
  • 那么以解出来的 $(x,y)$ 代替原来的坐标,问题就变成了每次可以向右或向上走一步,求方案数.
  • 如果没有障碍,答案显然是 $C_{x+y}^x$ .但现在有障碍.直接递推显然不行,因为新坐标可以达到 $2\times 500^2$ .
  • 考虑容斥.将障碍点,目标点视为关键点,做坐标转换(如果不是整数就直接舍去),然后排序.原点为第 $0$ 个关键点.
  • 设 $f(i)$ 表示从原点到达第 $i$ 个关键点而不经过其他关键点的方案数. $g(i,j)$ 表示从第 $i$ 个关键点到第 $j$ 个关键点的所有方案数.转移有 $f(i)=g(0,i)-\sum_{j=1}^{i-1} g(j,i)\cdot f(j)$ .而 $g$ 不需要考虑障碍,显然就是组合数.
  • 时间复杂度 $O(n^2)$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e6+10;
const int P=1e9+7;
const int inf=1e9;
inline int add(int a,int b)
{
	return (a + b >= P) ? (a + b - P) : (a + b);
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
typedef pair<int,int> pii;
const pii badp=make_pair(inf,inf);
int n,k=0,ax,ay,bx,by;
int ex=inf,ey=inf;
pii p[MAXN];
pii trans(int M,int N)
{
	int x,y;
	int up=ay*M-ax*N,down=bx*ay-by*ax;
	if(up%down || up/down<0)
		return badp;
	y=up/down;
	up=M*by-N*bx,down=ax*by-ay*bx;
	if(up%down || up/down<0)
		return badp;
	x=up/down;
	if(x>ex || y>ey)
		return badp;
	return make_pair(x,y);
}
int fac[MAXN],invfac[MAXN];
void init()
{
	int N=MAXN-10;
	fac[0]=1;
	for(int i=1;i<=N;++i)
		fac[i]=mul(fac[i-1],i);
	invfac[N]=fpow(fac[N],P-2);
	for(int i=N-1;i>=0;--i)
		invfac[i]=mul(invfac[i+1],i+1);
}
int C(int N,int M)
{
	return mul(fac[M],mul(invfac[N],invfac[M-N]));
}
int g(int i,int j)
{
	int x=p[j].first-p[i].first,y=p[j].second-p[i].second;
	if(x<0 || y<0)
		return 0;
	return C(x,x+y);
}
int f[MAXN];
int main()
{
	init();
	int Ex=read(),Ey=read();
	n=read(),ax=read(),ay=read(),bx=read(),by=read();
	p[++k]=trans(Ex,Ey);
	if(p[k]==badp)
	{
		puts("0");
		return 0;
	}
	ex=p[k].first,ey=p[k].second;
	for(int i=1;i<=n;++i)
	{
		int x=read(),y=read();
		pii tmp=trans(x,y);
		x=tmp.first,y=tmp.second;
		if(ex<x || ey<y)
			continue;
		assert(tmp!=badp);
		p[++k]=tmp;
	}
	p[0]=make_pair(0,0);
	++k;
	sort(p,p+k);
	f[0]=1;
	for(int i=1;i<k;++i)
	{
		f[i]=g(0,i);
		for(int j=1;j<i;++j)
			f[i]=add(f[i],P-mul(g(j,i),f[j]));
	}
	cout<<f[k-1]<<endl;
	return 0;
}