注意一个条件，ax*by!=bx*ay，所以每个点所需的每只手的次数是固定的，于是就可以转换为网格图（注意这里|坐标|<=500*500）中每次向上或向右走一步。因为障碍点较少，可以计算无法到达的方案数=先走到某一个障碍，再随便走。复杂度O（n*n）。
注意有一些无解的可能需要特判。//发现bzoj上使用cerr会返回RE 2333
#include<iostream> #include<cstdio> #include<algorithm> #define P 1000000007 #define ll long long using namespace std; int Ex,Ey,n,ax,ay,bx,by,b[505],inv[1000005],p[1000005],cnt; struct T { int x,y; }a[505],t; bool cmp(T a,T b) { return a.x!=b.x?a.x<b.x:a.y<b.y; } int C(int x,int y) { if (x==0) return 1; return (ll)p[y]*inv[y-x]%P*inv[x]%P; } int gcd(int x,int y) { return y?gcd(y,x%y):x; } T Get(int x,int y) { T ans; if ((x*by-y*bx)%(ax*by-ay*bx)) return (T){666666666,666666666}; ans.x=(x*by-y*bx)/(ax*by-ay*bx); if ((-x*ay+y*ax)%(ax*by-ay*bx)) return (T){666666666,666666666}; ans.y=(-x*ay+y*ax)/(ax*by-ay*bx); if (ans.x<0||ans.y<0) return (T){666666666,666666666}; return ans; } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); scanf("%d%d%d",&Ex,&Ey,&n); scanf("%d%d%d%d",&ax,&ay,&bx,&by); p[0]=1;p[1]=1;inv[0]=1;inv[1]=1; for (int i=2;i<=1000000;i++) p[i]=(ll)p[i-1]*i%P,inv[i]=(ll)(-P/i)*inv[P%i]%P; for (int i=2;i<=1000000;i++) inv[i]=(ll)inv[i]*inv[i-1]%P; //A*ax+B*bx=Ex //A*ay+B*by=Ey a[cnt=1]=Get(Ex,Ey); if (a[1].x==666666666||a[1].x<0||a[1].y<0) { puts("0"); return 0; } for (int i=1,x,y;i<=n;i++) { scanf("%d%d",&x,&y); t=Get(x,y); if (t.x<=a[1].x&&t.y<=a[1].y) a[++cnt]=t; } sort(a+1,a+cnt+1,cmp); for (int i=1;i<=cnt;i++) { //cerr<<a[i].x<<' '<<a[i].y<<endl; b[i]=C(a[i].x,a[i].x+a[i].y); //cout<<i<<' '<<b[i]<<endl; //cerr<<b[i]<<endl; for (int j=1;j<i;j++) if (a[j].x<=a[i].x&&a[j].y<=a[i].y) b[i]=(b[i]-(ll)b[j]*C(a[i].x-a[j].x,a[i].x+a[i].y-a[j].x-a[j].y)%P)%P; } printf("%d\n",(b[cnt]+P)%P); //system("pause"); }
