[20220324联考] 小 W 与骑士
前言
典中典中典之没做过典中典套路题两双手。
题目
如果从 \((x,y)\) 出发，每次可以走到 \((x+ax,y+ay)\) 或 \((x+bx,y+by)\)，起点是 \((0,0)\)，终点是 \((X,Y)\)，有 \(n\) 个点 \((x_i,y_i)\) 是障碍点不能走，问方案数，对 \(10^9+7\) 取模。如果路线无限多，输出 -1。
多组数据 \(T\le 5\)，期望所有数据的绝对值在 \(500\) 以内，但是数据有锅= =，但是对正解不影响。
讲解
看起来是究极讨论题，实际上有较少讨论的做法。
不平行
当然这里指的是 \((ax,ay)\) 和 \((bx,by)\) 两个向量不平行。
根据平面向量基本定理或者是其它什么的，我们知道一个向量 \((x,y)\) 会被不平行的两个向量 \(\vec{\alpha}=(ax,ay),\vec{\beta}=(bx,by)\) 唯一分解为 \((x,y)=p\vec{\alpha}+q\vec{\beta}\)。对不起球哥，我考试的时候连这个都没想起来qwq。
可以发现当 \(p,q\) 均为自然数时障碍物才有用，挑选出这些，按 \(p_i+q_i\) 从小到大排序，然后直接 \(O(n^2)\) dp 做容斥就好了。
平行
嘛，也就复杂了亿点点。但是卷爷有 nb 简单做法。
首先平行就变成了一维情况，我们设置一个 \(B\) 为一个比较大的值，然后把二维坐标映射到一维上，比如把 \((x,y)\) 映射为 \(B+x+y\)，可以发现这样相当合理。
然后从起点随便搜一下看能不能到终点，有没有环，先把 \(-1\) 和 \(0\) 判了。
然后卷爷是建图 bfs，但事实上直接 dfs 记忆化搜索就行了。
问题在于我不会克莱姆法则，分解向量的时候写得很麻烦。
代码
//12252024832524
#pragma GCC optimize("Ofast")
#include
#define TT template
using namespace std;
typedef long long LL;
const int MAXN = 505;
const int MOD = 1e9+7;
const int B = 500000;
int X,Y,n,ax,ay,bx,by;
int dp[MAXN];
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
int fac[1000005],ifac[1000005];
int qpow(int x,int y){
int ret = 1;
while(y){
if(y & 1) ret = 1ll * ret * x % MOD;
x = 1ll * x * x % MOD;
y >>= 1;
}
return ret;
}
void init(int x){
fac[0] = ifac[0] = 1;
for(int i = 1;i <= x;++ i) fac[i] = 1ll * fac[i-1] * i % MOD;
ifac[x] = qpow(fac[x],MOD-2);
for(int i = x-1;i >= 1;-- i) ifac[i] = ifac[i+1] * (i+1ll) % MOD;
}
LL C(int x,int y){
if(x < y || y < 0) return 0;
return 1ll * fac[x] * ifac[y] % MOD * ifac[x-y] % MOD;
}
struct point{
int x,y;
bool operator < (const point &px)const{
return x+y < px.x+px.y;
}
}p[MAXN];
void Get(point &A){
int x = A.x,y = A.y,d;
if(x * ay == y * ax){
if(ax) d = x / ax;
else d = y / ay;
if(ax * d == x && ay * d == y) A.x = d,A.y = 0;
else A.x = A.y = -1;
}
else if(x * by == y * bx){
if(bx) d = x / bx;
else d = y / by;
if(bx * d == x && by * d == y) A.x = 0,A.y = d;
else A.x = A.y = -1;
}
else{
int Q = (y * ax - x * ay) / (ax * by - bx * ay),P;
if(ax) P = (x - Q*bx) / ax;
else P = (y - Q*by) / ay;
if(P * ax + Q * bx == x && P * ay + Q * by == y) A.x = P,A.y = Q;
else A.x = A.y = -1;
}
}
/*
p ax + q bx = x
p ay + q by = y
(x - bx q) / ax = p
(x - bx q) ay + q ax by = y ax
q (ax by - bx ay) = y ax - x ay
*/
bool vis[B<<1|3],stp[B<<1|3],quan,ddd[B<<1|3];
bool check(int x){return x >= 0 && x <= (B<<1);}
bool dfs1(int x){
vis[x] = ddd[x] = 1;
bool ret = (x == B+X+Y);
// if(x >= B) printf("dfs1 %d %d\n",x,B+X+Y);
int to = x+ax+ay;
if(check(to)){
// if(to == 500030) printf("??????? %d %d %d\n",vis[to],stp[to],ddd[to]);
if(vis[to]) quan = 1;
else if(!stp[to] && !ddd[to]) ret |= dfs1(to);
}
to = x+bx+by;
if(check(to)){
if(vis[to]) quan = 1;
else if(!stp[to] && !ddd[to]) ret |= dfs1(to);
}
vis[x] = 0;
return ret;
}
int mem[B<<1|3];
bool wow[B<<1|3];
int dfs2(int x){
if(wow[x]) return mem[x];
int to = x-ax-ay,ret = 0;
if(check(to) && !stp[to]) ret = (ret + dfs2(to)) % MOD;
to = x-bx-by;
if((ax != bx || ay != by) && check(to) && !stp[to]) ret = (ret + dfs2(to)) % MOD;
wow[x] = 1;
return mem[x] = ret;
}
int main()
{
freopen("knight.in","r",stdin);
freopen("knight.out","w",stdout);
init(1e6);
for(int T = Read(); T ;-- T){
X = Read(); Y = Read(); n = Read();
ax = Read(); ay = Read(); bx = Read(); by = Read();
for(int i = 1;i <= n;++ i) p[i].x = Read(),p[i].y = Read(),dp[i] = 0;
if(ax * by == ay * bx){
if(ax * Y != ay * X) {Put(0,'\n');continue;}
memset(ddd,0,sizeof(ddd));
memset(stp,0,sizeof(stp));
for(int i = 1;i <= n;++ i) if(X * p[i].y == Y * p[i].x) stp[B+p[i].x+p[i].y] = -1;
quan = 0;
// printf("wrng\n");
if(!dfs1(B)) {Put(0,'\n');continue;}
if(quan){Put(-1,'\n');continue;}
memset(mem,0,sizeof(mem));
memset(wow,0,sizeof(wow));
mem[B] = 1; wow[B] = 1;
Put(dfs2(B+X+Y),'\n');
continue;
}
p[++n] = point{X,Y}; Get(p[n]);
if(p[n].x < 0 || p[n].y < 0){Put(0,'\n');continue;}
for(int i = 1;i < n;++ i) Get(p[i]);
sort(p+1,p+n);
for(int i = 1;i <= n;++ i)
if(p[i].x >= 0 && p[i].y >= 0){
dp[i] = C(p[i].x+p[i].y,p[i].x);
for(int j = 1;j < i;++ j)
if(p[j].x >= 0 && p[j].y >= 0)
dp[i] = ((dp[i] - dp[j] * C(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)) % MOD + MOD) % MOD;
}
Put(dp[n],'\n');
}
return 0;
}