记录编号	189255	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CodeChef KNGHTMOV] 骑士移动	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.654 s
提交时间	2015-09-26 19:36:59	内存使用	58.63 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZE=1010000;
const int SIZEN=1010;
const LL MOD=1e9+7;
void add(LL &a,LL &b){
    if(a==-1||b==-1) a=-1;
    else{
        a+=b;
        a%=MOD;
    }
}
LL inv[SIZE];//i的乘法逆元
LL fact[SIZE],invfact[SIZE];//阶乘及其乘法逆元
LL C(int a,int b){//组合数
	return fact[a]*invfact[b]%MOD*invfact[a-b]%MOD;
}
void prepare(void){//预先计算求组合数需要的数组
	inv[1]=1;
	for(int i=2;i<SIZE;i++) inv[i]=(MOD-(MOD/i))*inv[MOD%i]%MOD;//计算乘法逆元
	fact[0]=invfact[0]=1;
	for(int i=1;i<SIZE;i++){
		fact[i]=fact[i-1]*i%MOD;
		invfact[i]=invfact[i-1]*inv[i]%MOD;
	}
}
class Point{
public:
	int x,y;
};
bool operator < (const Point &a,const Point &b){
    return a.x+a.y<b.x+b.y;
}
bool depend(const Point &a,const Point &b){//两向量是否线性相关
	return a.x*b.y==a.y*b.x;
}
Point A,B,dest;
Point block[20];
int K;
void swap_xy(void){
    swap(A.x,A.y),swap(B.x,B.y),swap(dest.x,dest.y);
    for(int i=1;i<=K;i++) swap(block[i].x,block[i].y);
}
int solve_depend(void){//A,B线性相关
	if(!depend(A,dest)||!depend(B,dest)) return 0;//根本不可达
	//为什么要判两次呢?因为A,B中可能有0
	if(!A.x&&!A.y&&!B.x&&!B.y) return (!dest.x&&!dest.y)?-1:0;//A,B均为零,看dest是否为零
	if(!A.x){
	    if(A.y) swap_xy();
	    else if(B.x) swap(A,B);
	    else swap(A,B),swap_xy();
	}
	static LL dp[SIZEN*2+5][SIZEN*2+5];
    static bool reach[SIZEN*2+5][SIZEN*2+5];
    static bool neg[SIZEN*2];
	memset(dp,0,sizeof(dp));
	memset(reach,0,sizeof(reach));
	memset(neg,0,sizeof(neg));
	for(int i=1;i<=K;i++){
	    if(depend(block[i],A)&&depend(block[i],B)){
	        neg[block[i].x+SIZEN]=1;
	    }
	}
	dp[0][SIZEN]=(!A.x&&!A.y)||(!B.x&&!B.y)?-1:1;reach[0][SIZEN]=true;
	LL ans=0;
	for(int i=0;i<2*SIZEN;add(ans,dp[i][dest.x+SIZEN]),i++){
	    for(int j=-SIZEN,pos;j<=SIZEN;j++){
	        if(!neg[pos=j+SIZEN]){//该位置并无障碍
	            LL &val=dp[i][pos];
	            if(!reach[i][pos]) continue;
	            if(j>500||j<-500||i>1000) val=-1;//若能绕回dest必定有无数种,若回不来那-1也没用
	            if(pos+A.x>=0&&pos+A.x<=2*SIZEN){//走A
	                add(dp[i+1][pos+A.x],val);
	                reach[i+1][pos+A.x]=true;
	            }
	            if(A.x!=B.x&&pos+B.x>=0&&pos+B.x<=2*SIZEN){//走B
	                add(dp[i+1][pos+B.x],val);
	                reach[i+1][pos+B.x]=true;
	            }
	        }
	    }
	}
	return ans;
}
bool change_coor(Point &p){
    int det=A.y*B.x-A.x*B.y,a=p.y*B.x-p.x*B.y,b=p.x*A.y-p.y*A.x;
    if(a%det||b%det) return false;
    p.x=a/det,p.y=b/det;
    return true;
}
LL count(const Point &a,const Point &b){
    int x=b.x-a.x,y=b.y-a.y;
    if(x<0||y<0) return 0;
    return C(x+y,x);
}
int solve_independ(void){
    if(!change_coor(dest)) return 0;//若终点在坐标变换后不是整点
    if(dest.x<0||dest.y<0) return 0;//若终点不可达
    int n=0;
    for(int i=1;i<=K;i++){//同样对障碍进行变换
        if(change_coor(block[i])){
            if(block[i].x>=0&&block[i].y>=0) block[++n]=block[i];
        }
    }
    sort(block+1,block+1+n);//将障碍排序
    Point O=(Point){0,0};
    LL ans=count(O,dest);
    static LL dp[20];
    for(int i=1;i<=n;i++){
        dp[i]=count(O,block[i]);
        for(int j=1;j<i;j++){
            dp[i]=(dp[i]-dp[j]*count(block[j],block[i]))%MOD;//从i的方案中减去第一个走到j的方案
        }
        ans=(ans-dp[i]*count(block[i],dest))%MOD;
    }
    if(ans<0) ans+=MOD;
    return ans;
}
int solve(void){
    if(depend(A,B)) return solve_depend();
    else return solve_independ();
}
int main(void){
    freopen("knightmov.in","r",stdin);
    freopen("knightmov.out","w",stdout);
	prepare();
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&dest.x,&dest.y,&K);
		scanf("%d%d%d%d",&A.x,&A.y,&B.x,&B.y);
		for(int i=1;i<=K;i++) scanf("%d%d",&block[i].x,&block[i].y);
		printf("%d\n",solve());
	}
	return 0;
}