BZOJ 3782: 上学路线 [Lucas定理 DP]

3782: 上学路线

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 192 Solved: 75
[Submit][Status][Discuss]

Description

小C所在的城市的道路构成了一个方形网格，它的西南角为(0,0)，东北角为(N,M)。小C家住在西南角，学校在东北角。现在有T个路口进行施工，小C不能通过这些路口。小C喜欢走最短的路径到达目的地，因此他每天上学时都只会向东或北行走；而小C又喜欢走不同的路径，因此他问你按照他走最短路径的规则，他可以选择的不同的上学路线有多少条。由于答案可能很大，所以小C只需要让你求出路径数mod P的值。

Input

第一行，四个整数N、M、T、P。

接下来的T行，每行两个整数，表示施工的路口的坐标。

Output

一行，一个整数，路径数mod P的值。

HINT

1<=N,M<=10^10

0<=T<=200

p=1000003或p=1019663265

终于A掉了

这道题太可怕了

跟PoPoQQQ大爷的代码拍了好几组数据才改完Bug

首先想怎么算方案数

总-不合法

用容斥原理？好麻烦

发现一个点只会对$x,y$都比它大的点产生影响

$f[i]$表示走到点$i$不碰到其他点的方案数

$f[i]={x_i+y_i\choose x_i} - \sum\limits_{x_j<=x_i\ ,\ y_j<=y_i\ ,\ j\neq i}{x_i-x_j+y_i-y_j\choose x_i-x_j}*f[j] $

剩下的就是怎么计算组合数了

1000003直接用Lucas定理

1019663265和古代猪文一样是4个质数的乘积，Lucas定理+CRT合并

说一下问题：

1.DP时要时刻记住取模、

2.小心n和m溢出int

3.组合数n<m特判在用Lucas定理的时候不能丢！因为模意义下可能发生n<m!!!

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=1e6+;

inline ll read(){

    char c=getchar();ll x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

ll n,m,P;

int t;

struct Point{

    ll x,y;

    bool operator <(const Point &a)const{

        return x<a.x||(x==a.x&&y<a.y);

    }

}a[];

namespace A{

    ll P=;

    ll inv[N],fac[N],facInv[N];

    void ini(){

        inv[]=fac[]=facInv[]=;

        for(int i=;i<=P;i++){

            if(i!=) inv[i]=-P/i*inv[P%i]%P;

               inv[i]+=inv[i]<?P:;

            fac[i]=fac[i-]*i%P;

            facInv[i]=facInv[i-]*inv[i]%P;

        }

    }

    ll C(int n,int m){

        if(n<m) return ;

        return fac[n]*facInv[m]%P*facInv[n-m];

    }

    ll Lucas(ll n,ll m){

        if(n<m) return ;

        ll re=;

        for(;m;n/=P,m/=P) re=re*C(n%P,m%P)%P;

        return re;

    }

    ll f[];

    void dp(){

        for(int i=;i<=t;i++){

            f[i]=Lucas(a[i].x+a[i].y,a[i].x);//printf("fo %d %lld\n",i,f[i]);

            for(int j=;j<i;j++)

                if(a[j].x<=a[i].x&&a[j].y<=a[i].y)

                    f[i]=(f[i]- Lucas(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)*f[j]%P +P)%P;

                    //printf("oh %d %lld  %lld \n",j ,Lucas(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)*f[j]%P ,f[i]);

            //printf("f %d %lld\n",i,f[i]);

        }

    }

    void solve(){

        ini();

        dp();

        printf("%lld",f[t]);

    }

}

namespace B{

    ll P[]={,,,,};

    const int N=1e5+;

    ll Pow(ll a,ll b,ll P){

        if(a==) return ;

        ll re=;

        for(;b;b>>=,a=a*a%P)

            if(b&) re=re*a%P;

        return re;

    }

    ll Inv(ll a,ll P){return Pow(a,P-,P);}

    ll inv[N][],fac[N][],facInv[N][];

    void ini(){

        for(int j=;j<=;j++){

            int MOD=P[j];

            inv[][j]=fac[][j]=facInv[][j]=;

            for(int i=;i<=MOD;i++){

                if(i!=) inv[i][j]=-MOD/i*inv[MOD%i][j]%MOD;

                if(inv[i][j]<) inv[i][j]+=MOD;

                fac[i][j]=fac[i-][j]*i%MOD;

                facInv[i][j]=facInv[i-][j]*inv[i][j]%MOD;

            }

        }

    }

    ll C(int n,int m,int j){//printf("C %d %d %d  %lld %lld\n",n,m,j,fac[n][j],facInv[m][j]);

        if(n<m) return ;

        ll p=P[j];

        return fac[n][j]*facInv[m][j]%p*facInv[n-m][j]%p;

    }

    ll lucas(ll n,ll m,int j){

        if(n<m) return ;

        ll MOD=P[],a=,p=P[j];

        for(;m;m/=p,n/=p) a=a*C(n%p,m%p,j)%p;

        return a*(MOD/p)%MOD*Inv(MOD/p,p)%MOD;

    }

    ll Lucas(ll n,ll m){//printf("Lucas1 %lld %lld\n",n,m);

        ll re=,MOD=P[];

        for(int i=;i<=;i++)

            re=(re+lucas(n,m,i))%MOD;

        return re;

    }

    ll f[];

    void dp(){

        for(int i=;i<=t;i++){

            f[i]=Lucas(a[i].x+a[i].y,a[i].x);//printf("fo %d %lld\n",i,f[i]);

            for(int j=;j<i;j++)

                if(a[j].x<=a[i].x&&a[j].y<=a[i].y)

                    f[i]=(f[i]- Lucas(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)*f[j]%P[] +P[])%P[];

                    //printf("oh %d %lld  %lld \n",j ,Lucas(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x)*f[j] ,f[i]);

        //    printf("fn %d %lld\n",i,f[i]);

        }

    }

    void solve(){

        ini();

        dp();

        //for(int i=1;i<=t;i++)

        //    printf("Point %lld %lld  %lld\n",a[i].x,a[i].y,f[i]);

        printf("%lld",f[t]);

    }

}

int main(){

    freopen("in","r",stdin);

    n=read();m=read();

    t=read();P=read();

    for(int i=;i<=t;i++) a[i].x=read(),a[i].y=read();

    a[++t].x=n;a[t].y=m;

    sort(a+,a++t);

    if(P==) A::solve();

    else B::solve();

}

巴特西