达哥送分给我我都不要，感觉自己挺牛批。

$type=0:$

跟visit那题类似，枚举横向移动的步数直接推公式：

$ans=\sum C_n^i \times C_i^{\frac{i}{2}} \times C_{n-i}^{\frac{n-i}{2}},i\% 2=0$

$type=1:$

因为不能触碰负半轴，所以可以把右移看成+1，左移看成-1，转化为前缀和大于等于0的问题

于是直接Catalan数就好了。注意是第$\frac {n}{2}$项的Catalan。

$Catalan_n=C_{2n}^{n}-C_{2n}^{n-1}$

$type=2:$

观察到数据范围较小，考虑dp。

设$f[i]$为走i步回到原点的方案数，通过枚举第一次回到原点的步数j进行转移。

显然j只能为偶数。

$f[i]=\sum f[i-j]*Catalan(\frac{j}{2}-1)$

$type=3:$

还是枚举横向走的步数，结合Catalan数求解。

$ans=\sum C_n^i*Catalan(\frac{i}{2})*Catalan(\frac{n-i}{2})$

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const ll mod=;

const int N=;

int n,op;

ll fac[N<<],ans,dp[N<<];

ll qpow(ll a,ll b)

{

    ll res=;//a%=mod;

    while(b)

    {

        if(b&)res=res*a%mod;

        a=a*a%mod;

        b>>=;

    }

    return res;

}

ll ini()

{

    fac[]=;

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

        fac[i]=1LL*i*fac[i-]%mod;

}

ll C(ll x,ll y)

{

    if(y>x)return ;

    return fac[x]*qpow(fac[y],mod-)%mod*qpow(fac[x-y],mod-)%mod;

}

ll lucas(ll x,ll y)

{

    if(!y)return ;

    return C(x%mod,y%mod)*lucas(x/mod,y/mod)%mod;

}

ll Catalan(ll x)

{

    return (lucas(x*,x)-lucas(x*,x-)+mod)%mod;

}

void qj1()

{

    //cout<<2*n<<endl;

    //cout<<C(2*n,n)<<endl;

    ans=Catalan(1LL*n/);

    cout<<ans<<endl;

}

void qj0()

{

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

    {

        if(i%)continue;

        ans+=lucas(1LL*n,1LL*i)%mod*lucas(1LL*i,1LL*i/)%mod*lucas(1LL*(n-i),1LL*(n-i)/)%mod,ans%=mod;

    }

    cout<<ans<<endl;

}

void qj3()

{

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

    {

        if(i%)continue;

        ans+=lucas(1LL*n,1LL*i)*Catalan(1LL*i/)%mod*Catalan(1LL*(n-i)/)%mod,ans%=mod;

    }

    cout<<ans<<endl;

}

void qj2()

{

    dp[]=;

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

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

            dp[i]+=dp[i-j]*%mod*Catalan(1LL*j/-1LL)%mod,dp[i]%=mod;

    cout<<dp[n]<<endl;

}

int main()

{

    scanf("%d%d",&n,&op);

    ini();

    if(op==)qj1();

    else if(op==)qj0();

    else if(op==)qj3();

    else qj2();

    return ;

}

巴特西

[NOIP模拟测试9]题(Problem) 题解 (组合数全家桶+dp)

$type=0:$

$type=1:$

$type=2:$

$type=3:$

最新文章

热门文章