【bzoj4767】两双手

要开始做数数题了。

传送门

首先发现向量$\vec{a}(Ax,Ay)$和向量$\vec{b}(Bx,By)$不垂直，那么有平面向量基本定理，棋盘上所有的点都可以被唯一的表示为$x\vec{a}+y\vec{b}$，$(x,y)$就是它的新坐标，这图也就成了一个网格图。

问题变成了：求网格图有障碍路径条数。

如果没有障碍，从点$(a,b)$到点$(c,d)$的方案数就是$C_{c-a+d-b}^{c-a}$，那么把起点、终点和所有障碍点以跳跃次数为关键字排序。

设$f[i]$是原点到$i$不经过任何障碍的路径条数，$g[i][j]$表示$i$到$j$的路径条数。

所以$f[i]=g[0][i]-\sum_{j=1}^{i-1}f[j]*g[j][i]$

#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
#define mod 1000000007
using namespace std;
struct node{
    int x,y,z;
}t[520];
int n,m,k,a1,b1,a2,b2,cnt;
ll f[520],g[520][520],jc[500001],ny[500001],so[500001];
inline bool cmp(node c,node d){return c.z<d.z;}
inline ll C(int x,int y){return jc[y]%mod*ny[y-x]%mod*ny[x]%mod;}
inline void calc(int &x,int &y){
    int mo1=x*b2-y*a2,mo2=x*b1-y*a1;
    int de1=a1*b2-b1*a2,de2=a2*b1-a1*b2;
    if (!de1||!de2){x=y=-1; return;}
    if (mo1%de1||mo2%de2){x=y=-1; return;}
    x=mo1/de1,y=mo2/de2;
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    scanf("%d%d%d%d",&a1,&b1,&a2,&b2);
    calc(n,m); int x,y;
    t[++cnt].x=n,t[cnt].y=m; t[cnt].z=n+m;
    if (n<0){puts("0"); return 0;}
    for (int i=1; i<=k; i++){
        scanf("%d%d",&x,&y);
        calc(x,y);
        if (x<0||y<0||x>n||y>m) continue;
        t[++cnt].x=x; t[cnt].y=y; t[cnt].z=x+y;
    }
    jc[1]=so[1]=ny[1]=jc[0]=ny[0]=1;
    for (int i=2; i<=n+m; i++){
        jc[i]=jc[i-1]*i%mod;
        so[i]=(mod-mod/i)*so[mod%i]%mod;
        ny[i]=ny[i-1]*so[i]%mod;
    }
    sort(t+1,t+cnt+1,cmp);
    for (int i=1; i<=cnt; i++)
        for (int j=0; j<i; j++){
//			x=t[i].x-t[j].x,y=t[i].x-t[j].x+t[i].y-t[j].y;
//			g[j][i]=jc[y]%mod*ny[y-x]%mod*ny[x]%mod;
            g[j][i]=C(t[i].x-t[j].x,t[i].x-t[j].x+t[i].y-t[j].y)%mod;
//			printf("%d %d: %lld\n",j,i,g[j][i]);
        }
    f[0]=1;// printf("%lld\n",g[1][2]);
    for (int i=1; i<=cnt; i++){
        f[i]=g[0][i];
        for (int j=1; j<i; j++)
            f[i]=(f[i]-f[j]*g[j][i]%mod+mod)%mod;
    }
    printf("%lld\n",f[cnt]);
    return 0;
}
/*
4 4 1
0 1 1 0
2 3
*/