bzoj4767 两双手

bzoj4767 两双手

​​ Description 老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)的值就行。

Input 第一行三个整数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

Output 仅一行一个整数，表示所求的答案。

Sample Input 4 4 1 0 1 1 0 2 3 Sample Output 40 HINT

Source 因为题目有特殊限制 所以列出方程发现我们可以唯一的用几步1走法+几步2走法 走到一个位置

那么就把这个几步当做 向量来看即可 这就变成了 每次只能往上往右走的dp套路题

注意最终的位置可能算出的向量并非最大 所以不能提前算出 一起排序

#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if(T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int mod=1e9+7;const int N=5e5+10;struct node{ int x,y;}p[550];int jc[N],inv[N],n,ex,ey,ax,ay,bx,by,dp[550];inline void dec(int &x,int v){x=x-v<0?x-v+mod:x-v;}inline int ksm(ll b,int t){static ll tmp; for (tmp=1;t;b=b*b%mod,t>>=1) if(t&1) tmp=tmp*b%mod;return tmp;}inline bool cmp(const node &a,const node &b){ return a.x==b.x?a.y=p[j].y) dec(dp[i],(ll)dp[j]*C(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)%mod); }printf("%d\n",dp[n]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。