BZOJ 3782 上学路线 ——动态规划 Lucas定理中国剩余定理

我们枚举第一个经过的坏点，然后DP即可。

状态转移方程不是难点，难点在于组合数的处理。

将狼踩尽的博客中有很详细的证明过程，但是我只记住了结论

$n=a_1 * p^k+a_2*p^k-1...$

$m=b_1 * p^k+b_2*p^k-1...$

$C(_{m}^{n})=C(_{b_1}^{a_1})*...$

大概的意思就是转化成$p$进制下的每一位做组合数，那么我们就可以预处理阶乘以及它的逆元进行计算。

所以说Lucas只能跑过$10^5$当质数很大的时候就放弃。

如果不是质数，那么可以分解质因数，每一个因数做一次Lucas，然后用CRT合并。

以前留下的大坑终于补完了，EXGCD和CRT终于明白了（真是弱(。・・)ノ）

突然发现namespace写起来挺好用的，以后挂链就用它了

注意 1.n<m时候需要判定，因为%意义下会有小的情况产生。

2.随时取模

#include <map>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)

#define D(i,j,k) for (int i=j;i>=k;--i)

#define ll long long

#define mp make_pair

namespace Subtask1{

    const int p=1000003;

    ll fac[p],inv[p];

    void Shaker()

    {

        int i;

        for (fac[0]=1,i=1;i<p;++i)

            fac[i]=fac[i-1]*i%p;

        for (inv[1]=1,i=2;i<p;++i)

            inv[i]=(p-p/i)*inv[p%i]%p;

        for (inv[0]=1,i=1;i<p;++i)

            (inv[i]*=inv[i-1])%=p;

    }

    ll C(ll n,ll m)

    {

        if (n<m) return 0;

        if (n<p&&m<p) return fac[n]*inv[m]*inv[n-m]%p;

        return C(n%p,m%p)*C(n/p,m/p)%p;

    }

}

namespace Subtask2{

    const int p=1019663265;

    int pri[]={3,5,6793,10007};

    ll fac[4][10007],inv[4][10007],k1=339887755,k2=407865306,k3=673070820,k4=618502650;

    void Shaker()

    {

        int i,j;

        for (j=0;j<4;++j)

        {

            int np=pri[j];

            for (fac[j][0]=1,i=1;i<np;++i)

                fac[j][i]=fac[j][i-1]*i%np;

            for (inv[j][1]=1,i=2;i<np;++i)

                inv[j][i]=(np-np/i)*inv[j][np%i]%np;

            for (inv[j][0]=1,i=1;i<np;++i)

                (inv[j][i]*=inv[j][i-1])%=np;

        }

    }

    ll C(ll n,ll m,int j)

    {

        int np=pri[j];

        if (n<m) return 0;

        if (n<np&&m<np) return fac[j][n]*inv[j][m]*inv[j][n-m]%np;

        return C(n%np,m%np,j)*C(n/np,m/np,j)%np;

    }

    ll C(ll n,ll m)

    {

        ll r1=C(n,m,0),r2=C(n,m,1),r3=C(n,m,2),r4=C(n,m,3);

        return (r1*k1+r2*k2+r3*k3+r4*k4)%p;

    }

}

struct Point{

    ll x,y;

    void read(){scanf("%lld%lld",&x,&y);}

}points[220];

bool cmp(Point a,Point b)

{return a.x==b.x?a.y<b.y:a.x<b.x;}

ll ksm(ll a,ll b,ll p)

{

    ll ret=1;

    for (;b;b>>=1,(a*=a)%=p)

        if (b&1) (ret*=a)%=p;

    return ret;

}

ll f[220],t,n,m;

void solve1()

{

    using namespace Subtask1;

    Shaker();

    F(i,1,t)

    {

        f[i]=C(points[i].x+points[i].y,points[i].x);

        F(j,1,i-1) if (points[j].y<=points[i].y)

        {

            (f[i]-=f[j]*C(points[i].x-points[j].x+points[i].y-points[j].y,points[i].x-points[j].x)%p);

            f[i]+=p; f[t]%=p;

        }

    }

}

void solve2()

{

    using namespace Subtask2;

    Shaker();

    F(i,1,t)

    {

        f[i]=C(points[i].x+points[i].y,points[i].x);

        F(j,1,i-1) if (points[j].y<=points[i].y)

        {

            (f[i]-=f[j]*C(points[i].x-points[j].x+points[i].y-points[j].y,points[i].x-points[j].x)%p);

            f[i]%=p;f[i]+=p; f[t]%=p;

        }

    }

}

void Finout()

{

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

    freopen("wa.txt","w",stdout);

}

int main()

{

    ll p;

    scanf("%lld%lld%lld%lld",&n,&m,&t,&p);

    F(i,1,t) points[i].read();++t;points[t].x=n;points[t].y=m;

    sort(points+1,points+t+1,cmp);

    if (p==1000003) solve1(); else solve2();

    cout<<f[t]<<endl;

}

巴特西

BZOJ 3782 上学路线 ——动态规划 Lucas定理中国剩余定理

最新文章

热门文章

巴特西

BZOJ 3782 上学路线 ——动态规划 Lucas定理 中国剩余定理

最新文章

热门文章

BZOJ 3782 上学路线 ——动态规划 Lucas定理中国剩余定理