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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e6+5;
inline ll read(){
    char c=getchar();ll 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;
}
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[205];
namespace A{
    ll P=1000003;
    ll inv[N],fac[N],facInv[N];
    void ini(){
        inv[1]=fac[0]=facInv[0]=1;
        for(int i=1;i<=P;i++){
            if(i!=1) inv[i]=-P/i*inv[P%i]%P;
               inv[i]+=inv[i]<0?P:0;
            fac[i]=fac[i-1]*i%P;
            facInv[i]=facInv[i-1]*inv[i]%P;
        }
    }
    ll C(int n,int m){
        if(n<m) return 0;
        return fac[n]*facInv[m]%P*facInv[n-m];
    }
    ll Lucas(ll n,ll m){
        if(n<m) return 0;
        ll re=1;
        for(;m;n/=P,m/=P) re=re*C(n%P,m%P)%P;
        return re;
    }
    ll f[205];
    void dp(){
        for(int i=1;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=1;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[5]={1019663265,3,5,6793,10007};
    const int N=1e5+5;
    ll Pow(ll a,ll b,ll P){
        if(a==0) return 0;
        ll re=1;
        for(;b;b>>=1,a=a*a%P)
            if(b&1) re=re*a%P;
        return re;
    }
    ll Inv(ll a,ll P){return Pow(a,P-2,P);}
    ll inv[N][5],fac[N][5],facInv[N][5];
    void ini(){
        for(int j=1;j<=4;j++){
            int MOD=P[j];
            inv[1][j]=fac[0][j]=facInv[0][j]=1;
            for(int i=1;i<=MOD;i++){
                if(i!=1) inv[i][j]=-MOD/i*inv[MOD%i][j]%MOD;
                if(inv[i][j]<0) inv[i][j]+=MOD;
                fac[i][j]=fac[i-1][j]*i%MOD;
                facInv[i][j]=facInv[i-1][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 0;
        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 0;
        ll MOD=P[0],a=1,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=0,MOD=P[0];
        for(int i=1;i<=4;i++)
            re=(re+lucas(n,m,i))%MOD;
        return re;
    }
     
    ll f[205];
    void dp(){
        for(int i=1;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=1;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[0] +P[0])%P[0];
                    //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=1;i<=t;i++) a[i].x=read(),a[i].y=read();
    a[++t].x=n;a[t].y=m;
    sort(a+1,a+1+t);
    if(P==1000003) A::solve();
    else B::solve();
}