首页 > 代码库 > [BZOJ 4767]两双手（组合数学+Dp）
[BZOJ 4767]两双手（组合数学+Dp）
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)的值就行。
Solution
Ax*By-Ay*Bx≠0所以向量A、B的步数是固定的，走法也就有C(m+n,m)种
先对障碍点排序
Dp，f[i]表示到达障碍点i且不经过其他障碍点的方案数（用容斥减去经过其他障碍点的方案数）
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#define Mod 1000000007#define MAXN 500005typedef long long LL;using namespace std;int n,ax,ay,bx,by;LL fac[MAXN],inv[MAXN],f[MAXN];struct Node{ int x,y;}p[MAXN];void init(){ fac[0]=1,inv[1]=1; for(int i=1;i<MAXN;i++) fac[i]=(fac[i-1]*i)%Mod; for(int i=2;i<MAXN;i++) inv[i]=((Mod-Mod/i)*inv[Mod%i])%Mod; inv[0]=1; for(int i=1;i<=MAXN;i++) inv[i]=(inv[i]*inv[i-1])%Mod;}LL C(LL x,LL y){ if(x<y)return 0; return ((fac[x]*inv[y])%Mod*inv[x-y])%Mod;}bool cmp(Node A,Node B){ if(A.x==B.x)return A.y<B.y; return A.x<B.x; }void calc(int &x,int &y){ int m,n; if((ay*x-ax*y)%(bx*ay-ax*by)){x=-1,y=-1;return;} n=(ay*x-ax*y)/(bx*ay-ax*by); if((by*x-bx*y)%(ax*by-bx*ay)){x=-1,y=-1;return;} m=(by*x-bx*y)/(ax*by-bx*ay); x=m,y=n;}int main(){ init(); scanf("%d%d%d",&p[0].x,&p[0].y,&n); scanf("%d%d%d%d",&ax,&ay,&bx,&by); calc(p[0].x,p[0].y); for(int i=1;i<=n;i++) { scanf("%d%d",&p[i].x,&p[i].y); calc(p[i].x,p[i].y); } sort(p+1,p+1+n,cmp); p[n+1]=p[0]; for(int i=1;i<=n+1;i++) { if(p[i].x==-1)continue; f[i]=C(p[i].x+p[i].y,p[i].x); for(int j=1;j<i;j++) f[i]=(f[i]-f[j]*C(p[i].x-p[j].x+p[i].y-p[j].y,p[i].x-p[j].x)%Mod+Mod)%Mod; } printf("%lld\n",f[n+1]); return 0;}
[BZOJ 4767]两双手（组合数学+Dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。