首页 > 代码库 > [BZOJ4767]两双手
[BZOJ4767]两双手
[BZOJ4767]两双手
试题描述
老W是个棋艺高超的棋手,他最喜欢的棋子是马,更具体地,他更加喜欢马所行走的方式。老W下棋时觉得无聊,便决定加强马所行走的方式,更具体地,他有两双手,其中一双手能让马从(u,v)移动到(u+Ax,v+Ay)而另一双手能让马从(u,v)移动到(u+Bx,v+By)。小W看见老W的下棋方式,觉得非常有趣,他开始思考一个问题:假设棋盘是个无限大的二维平面,一开始马在原点(0,0)上,若用老W的两种方式进行移动,他有多少种不同的移动方法到达点(Ex,Ey)呢?两种移动方法不同当且仅当移动步数不同或某一步所到达的点不同。老W听了这个问题,觉得还不够有趣,他在平面上又设立了n个禁止点,表示马不能走到这些点上,现在他们想知道,这种情况下马有多少种不同的移动方法呢?答案数可能很大,你只要告诉他们答案模(10^9+7)的值就行。
输入
第一行三个整数Ex,Ey,n分别表示马的目标点坐标与禁止点数目。
第二行四个整数Ax,Ay,Bx,By分别表示两种单步移动的方法,保证Ax*By-Ay*Bx≠0
接下来n行每行两个整数Sxi,Syi,表示一个禁止点。
|Ax|,|Ay|,|Bx|,|By| <= 500, 0 <= n,Ex,Ey <= 500
输出
仅一行一个整数,表示所求的答案。
输入示例
4 4 1 0 1 1 0 2 3
输出示例
40
数据规模及约定
见“输入”
题解
容斥原理 + dp。。。感觉自己对这套理论不是很熟悉。。。
最开始时先把坐标转化一下,就是对于每个向量 p 解一个方程 p = x · a + y · b。
先把点按照坐标 (x, y) 字典序排序,设 f(i) 表示到达第 i 个点并且不经过任何其他点的方案数,那么转移时可以枚举最先碰到的点然后容斥。具体来说,最开始假设不考虑任何点那么方案数就是 C(xi + yi, xi),若最先碰到的点为 j,那么被容斥掉的方案数就是 f(j) · C(xi - xj + yi - yj, xi - xj),然后对于所有的 j 都减掉这样多余的方案数就好了。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> using namespace std; int read() { int x = 0, f = 1; char c = getchar(); while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); } while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); } return x * f; } #define maxn 510 #define maxl 500010 #define MOD 1000000007 #define LL long long struct Vec { int x, y; Vec() {} Vec(int _, int __): x(_), y(__) {} int operator ^ (const Vec& t) const { return x * t.y - y * t.x; } bool operator < (const Vec& t) const { return x != t.x ? x < t.x : y < t.y; } } A, B, ps[maxn], End, sol[maxn]; Vec trans(Vec a, Vec b, Vec p) { if((p ^ b) % (a ^ b)) return Vec(-233, -233); int x = (p ^ b) / (a ^ b); if(!b.x || (p.x - a.x * x) % b.x) { if(!b.y || (p.y - a.y * x) % b.y) return Vec(-233, -233); return Vec(x, (p.y - a.y * x) / b.y); } return Vec(x, (p.x - a.x * x) / b.x); } int n, cnt; void gcd(LL a, LL b, LL& x, LL& y) { if(!b){ x = 1; y = 0; return ; } gcd(b, a % b, y, x); y -= a / b * x; return ; } LL Inv(LL a) { LL x, y; gcd(a, MOD, x, y); return (x % MOD + MOD) % MOD; } LL fact[maxl], ifact[maxl]; void init() { fact[0] = 1; for(int i = 1; i < maxl; i++) fact[i] = fact[i-1] * i % MOD; ifact[0] = 1; for(int i = 1; i < maxl; i++) ifact[i] = ifact[i-1] * Inv(i) % MOD; return ; } LL C(int a, int b) { return (fact[a] * ifact[a-b] % MOD) * ifact[b] % MOD; } LL f[maxn]; int main() { End.x = read(); End.y = read(); n = read(); A.x = read(); A.y = read(); B.x = read(); B.y = read(); for(int i = 1; i <= n; i++) ps[i].x = read(), ps[i].y = read(); End = trans(A, B, End); if(End.x < 0 || End.y < 0) return puts("0"), 0; for(int i = 1; i <= n; i++) { ps[i] = trans(A, B, ps[i]); if(ps[i].x >= 0 && ps[i].y >= 0) sol[++cnt] = ps[i]; } sort(sol + 1, sol + cnt + 1); init(); sol[++cnt] = End; for(int i = 1; i <= cnt; i++) { f[i] = C(sol[i].x + sol[i].y, sol[i].x); LL sum = 0; for(int j = 1; j < i; j++) if(sol[j].x <= sol[i].x && sol[j].y <= sol[i].y) (sum += f[j] * C(sol[i].x + sol[i].y - sol[j].x - sol[j].y, sol[i].x - sol[j].x) % MOD) %= MOD; f[i] = (f[i] - sum + MOD) % MOD; } printf("%lld\n", f[cnt]); return 0; }
[BZOJ4767]两双手
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。