当前位置：首页 > news >正文

BZOJ 4767: 两双手 [DP 组合数]

news 来源：原创 2024/4/30 22:13:45

传送门

题意：

给你平面上两个向量，走到指定点，一些点不能经过，求方案数

煞笔提一开始被题面带偏了一直郁闷为什么方案不是无限

现在精简的题意.....不就是$bzoj3782$原题嘛，还不需要$Lucas$了....

因为这是平面向量啊

基本定理与唯一表示.....

小新上课强调了辣么多次......

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=505,M=1e6,P=1e9+7;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int x,y,n,x1,y1,x2,y2;
struct Point{
    int x,y;
    bool operator <(const Point &r)const{return x<r.x || (x==r.x && y<r.y);}
}a[N];
int m;
bool solEqu(int x,int y,Point &p){//printf("solEqu %d %d\n",x,y);
    int a=x*y1-y*x1,b=x2*y1-y2*x1;//printf("a b %d %d\n",a,b);
    if(a%b) return 0;else p.x=a/b;
    a=x*y2-y*x2,b=x1*y2-y1*x2;//printf("a b %d %d\n",a,b);
    if(a%b) return 0;else p.y=a/b;//printf("Point %d %d\n",p.x,p.y);
    return 1;
}
ll inv[M],fac[M],facInv[M];
void ini(int n){
    inv[1]=1;fac[0]=facInv[0]=1;
    for(int i=1;i<=n;i++){
        if(i!=1) inv[i]=(P-P/i)*inv[P%i]%P;
        fac[i]=fac[i-1]*i%P;
        facInv[i]=facInv[i-1]*inv[i]%P;
    }
}
inline ll C(int n,int m){return fac[n]*facInv[m]%P*facInv[n-m]%P;}
ll f[N];
inline void modify(ll &x){if(x<0) x+=P;}
void dp(){
    for(int i=1;i<=m;i++){
        f[i]=C(a[i].x+a[i].y,a[i].x);
        for(int j=1;j<i;j++) if(a[j].x<=a[i].x && a[j].y<=a[i].y)
            modify(f[i]-=C(a[i].x-a[j].x+a[i].y-a[j].y , a[i].x-a[j].x) * f[j] %P);
    }
}
int main(){
    freopen("in","r",stdin);
    ini(500000);
    x=read();y=read();n=read();
    x1=read();y1=read();x2=read();y2=read();
    if(!solEqu(x,y,a[++m])) {puts("0");return 0;}
    for(int i=1;i<=n;i++){
        x=read();y=read();
        if(!solEqu(x,y,a[++m]) || a[m].x>a[1].x || a[m].y>a[1].y) m--;
    }
    sort(a+1,a+1+m);
    dp();
    printf("%lld",f[m]);
}