首页 > 代码库 > Bzoj4767 两双手

Bzoj4767 两双手

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 553  Solved: 160

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

 

说起来,为什么是两双手不是两只手啊

 

数学问题 动规 向量 容斥

很明显,A、B两向量不共线的话,从起点到终点这一向量可以被A、B两向量唯一表示。

愉快地解个方程吧,设A用了X次,B用了Y次,终点为(Ex,Ey)

$ Ax * X + Bx * Y =Ex $

$ Ay * X + By * Y =Ey $

解出来就是代码里那个样子(逃)

总共X+Y步,假设从中选Y步使用B向量,那么剩下的步就是A向量,所以方案数总共有 $ G[i]=C_{X+Y}^{Y} $ 种

由于路上有障碍,所以需要减掉不合法的方案数。

对于每个障碍点i,枚举在它之前走过的点j,合法方案数 $ F[i]= G[i]-\sum_{j=1}^{i-1}F[j]*g[j][i] $ ←g[j][i]表示从j到i(中间没有路障)的方案数

 

刚开始写了即时算步数并计算方案数,然而好像出现了微妙的容斥错误,最后一个点过不去。

死活调不对,不得已换成了一开始就离散化出到达每个点需要步数的写法

 

技术分享
  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 #define LL long long  9 using namespace std; 10 const int mod=1e9+7; 11 const int mxn=1200000; 12 int read(){ 13     int x=0,f=1;char ch=getchar(); 14     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();} 15     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();} 16     return x*f; 17 } 18 struct point{ 19     int x,y; 20     bool operator < (const point b)const{return x<b.x;} 21 }s[mxn]; 22 int n,Ex,Ey; 23 int ax,ay,bx,by; 24 int SA,SB; 25 LL fac[mxn]; 26 LL inv[mxn]; 27 void init(){ 28     fac[1]=1;inv[1]=1; 29     fac[0]=1;inv[0]=1; 30     for(int i=2;i<mxn;i++){ 31         fac[i]=(LL)fac[i-1]*i%mod; 32         inv[i]=((-mod/i)*inv[mod%i]%mod+mod)%mod; 33     } 34     for(int i=2;i<mxn;i++) inv[i]=inv[i]*inv[i-1]%mod; 35 //  for(int i=1;i<=100;i++)printf("i:%d %lld\n",i,inv[i]); 36     return; 37 } 38 bool GST(int u,int v){ 39     int x0=s[v].x-s[u].x; 40     int y0=s[v].y-s[u].y; 41     int a=x0*ay-y0*ax,b=bx*ay-by*ax; 42     if(a%b)return 0;else SA=a/b; 43     a=x0*by-y0*bx,b=ax*by-ay*bx; 44     if(a%b)return 0;else SB=a/b; 45     return 1; 46       47 /*  int tmp=y0*ax-x0*ay; 48     int t2=ax*by-ay*bx; 49     if(tmp%t2)return 0; 50     else SB=tmp/t2; 51     tmp=y0*bx-x0*by; 52     t2=bx*ay-by*ax; 53     if(tmp%t2)return 0; 54     else SA=tmp/t2; 55     return 1;*/ 56 } 57 inline LL calc(int n,int m){ 58     if(n<m)return 0; 59     return fac[n]*inv[m]%mod*inv[n-m]%mod; 60 } 61 LL f[mxn]; 62 void solve(){ 63     int i,j; 64 //  printf("%d %d %d %d\n",ax,ay,bx,by); 65     for(i=1;i<=n;i++){ 66         if(!GST(0,i))continue; 67 //      printf("x:%d y:%d\n",s[i].x,s[i].y); 68 //      printf("SA:%d SB:%d\n",SA,SB); 69         f[i]=calc(SA+SB,SA); 70         for(j=1;j<i;j++){ 71 //          if(s[j].x<=s[i].x && s[j].y<=s[i].y){ 72                 if(!GST(j,i))continue; 73 //              printf("j%d:SA:%d SB:%d %lld\n",j,SA,SB,calc(SA+SB,SA)); 74                 f[i]=(f[i]-(f[j]*calc(SA+SB,SA))%mod+mod)%mod; 75 //          } 76         } 77 //      printf("f[%d]:%lld\n",i,f[i]); 78     } 79     printf("%lld\n",f[n]); 80     return; 81 } 82 int main(){ 83 //  freopen("in.txt","r",stdin); 84     init(); 85     int i,j; 86     Ex=read();Ey=read();n=read(); 87     ax=read();ay=read();bx=read();by=read(); 88     for(i=1;i<=n;i++){ 89         s[i].x=read(),s[i].y=read(); 90 /*      if(s[i].x>Ex || s[i].y>Ey){ 91             i--;n--; 92         }*/ 93     } 94     ++n;s[n].x=Ex,s[n].y=Ey; 95     if(!GST(0,n)){ 96         printf("0\n");return 0; 97     } 98     sort(s+1,s+n); 99     solve();100     return 0;101 }
WA掉的代码

 

 

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 #define LL long long  9 using namespace std; 10 const int mod=1e9+7; 11 const int mxn=1200000; 12 int read(){ 13     int x=0,f=1;char ch=getchar(); 14     while(ch<0 || ch>9){if(ch==-)f=-1;ch=getchar();} 15     while(ch>=0 && ch<=9){x=x*10+ch-0;ch=getchar();} 16     return x*f; 17 } 18 struct point{ 19     int x,y;bool ban; 20     bool operator < (const point b)const{ 21         return (x<b.x)||(x==b.x && y==b.y); 22     } 23 }s[mxn]; 24 int n,Ex,Ey; 25 int ax,ay,bx,by; 26 int SA,SB; 27 LL fac[mxn]; 28 LL inv[mxn]; 29 void init(){ 30     fac[1]=1;inv[1]=1; 31     fac[0]=1;inv[0]=1; 32     for(int i=2;i<mxn;i++){ 33         fac[i]=(LL)fac[i-1]*i%mod; 34         inv[i]=((-mod/i)*inv[mod%i]%mod+mod)%mod; 35     } 36     for(int i=2;i<mxn;i++) inv[i]=inv[i]*inv[i-1]%mod; 37     return; 38 } 39 bool ban[mxn]; 40 bool GST(int u,int v){ 41     int x0=s[v].x-s[u].x; 42     int y0=s[v].y-s[u].y; 43 /*    int a=x0*ay-y0*ax,b=bx*ay-by*ax; 44     if(a%b)return 0;else SA=a/b; 45     a=x0*by-y0*bx,b=ax*by-ay*bx; 46     if(a%b)return 0;else SB=a/b; 47     return 1;*/ 48     int tmp=y0*ax-x0*ay; 49     int t2=ax*by-ay*bx; 50     if(tmp%t2)return 0; 51     else SB=tmp/t2; 52     tmp=y0*bx-x0*by; 53     t2=bx*ay-by*ax; 54     if(tmp%t2)return 0; 55     else SA=tmp/t2; 56     return 1; 57 } 58 inline LL calc(int n,int m){ 59     if(n<m)return 0; 60     return fac[n]*inv[m]%mod*inv[n-m]%mod; 61 } 62 LL f[mxn]; 63 void solve(){ 64     int i,j; 65     for(i=1;i<=n;i++){ 66         f[i]=calc(s[i].x+s[i].y,s[i].x); 67         for(j=1;j<i;j++){ 68             if(s[j].x<=s[i].x && s[j].y<=s[i].y){ 69                 f[i]=(f[i]-(f[j]*calc(s[i].x-s[j].x+s[i].y-s[j].y,s[i].x-s[j].x))%mod+mod)%mod; 70             } 71         } 72 //        printf("f[%d]:%lld\n",i,f[i]); 73     } 74     printf("%lld\n",f[n]); 75     return; 76 } 77 int main(){ 78 //    freopen("in.txt","r",stdin); 79     init(); 80     int i,j; 81     Ex=read();Ey=read();n=read(); 82     ax=read();ay=read();bx=read();by=read(); 83     for(i=1;i<=n;i++){ 84         s[i+1].x=read(),s[i+1].y=read(); 85     } 86     ++n;s[1].x=Ex,s[1].y=Ey; 87     if(!GST(0,1)){ 88         printf("0\n");return 0; 89     } 90     s[1].x=SA;s[1].y=SB; 91     int cnt=1; 92     for(i=2;i<=n;i++){ 93         if(!GST(0,i))continue; 94         s[++cnt].x=SA;s[cnt].y=SB; 95         if(s[cnt].x>s[1].x || s[cnt].x>s[1].y)cnt--; 96     } 97     n=cnt; 98     sort(s+1,s+n+1); 99     solve();100     return 0;101 }

 

Bzoj4767 两双手