题解 题

· · 个人记录

T3 题

解题思路

一看这题名字挺奇怪，网上一搜，是一套题（简，单，题）好像时学长出的，因为简太水了，就被教练踢掉了。

看见这个题的第一思路先是DP，随后想了想排列组合好像更好一些，最后一看时间不够了，先打了一个样例（5pts）然后就是大暴力了。

下面就是正解了：

typ=0

枚举横向移动了多少步。

横向移动i步时(为了存在合法解,i必须是偶数)，纵向的显然就是n-i了，横向方案数为C_i^{\frac{i}{2}}(来回随便走i步里面选\dfrac{i}{2}步

纵向就是C_{n-i}^{\frac{n-i}{2}}，和横向的式子差不多。

然后从n步里选i步，乘上一个C_n^i就好了。

typ=1

从\dfrac{n}{2}个-1和\dfrac{n}{2}个1里排列一下，这不就是个Catalan序列吗 （虽然我是现学的） 。

typ=2

这里就用上DP了

f[i]表示走了i步回到原点的方案数（中途可能回到过原点多次

枚举第一次回到原点时走过的步数j(为了存在合法解,j为偶数)

则此时方案数为f[i-j]*Catalan(j/2-1)

第 j 步第一次回到原点，之后可能有多次再次回原点f[i-j]，

在计算这 j 步时，我们必须保证 j 步中不回原点，所以Catalan(j/2-1)

这个 -1 就是保证栈不为空 (左右移动可以看作栈)

typ=3

与typ=1的做法有一点类似。

枚举横向移动了多少步

横向移动 i 步时(为了存在合法解, i 必须是偶数)

方案数为C_n^i*Catalan(\dfrac{i}{2})*Catalan(\dfrac{n-i}{2})

代码优化

因为要取模，就一定要计算 inv ，又可以发现我们用的所有inv都是阶乘，因此我们可以直接把inv初始化阶乘。对于其他的快速幂一下就好了。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10,mod=1e9+7;
int n,ans,task,f[N],jc[N<<1],inv[N<<1];
void get_Jc()
{
    jc[0]=1;
    for(int i=1;i<(N<<1);i++)
        jc[i]=jc[i-1]*i%mod;
}
void get_Inv()
{
    inv[0]=inv[1]=1;
    for(int i=2;i<(N<<1);i++)
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<(N<<1);i++)
        inv[i]=inv[i]*inv[i-1]%mod;
}
int ksm(int x,int y)
{
    int ans=1;
    while(y)
    {
        if(y&1)
            ans=ans*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return ans;
}
int C(int i,int j)
{
    if(i>j)
        return 0;
    if(i==0||j==0)
        return 1;
    return jc[j]%mod*inv[i]%mod*inv[j-i]%mod;
}
int Catalan(int x)
{
    return C(x,x<<1)%mod*ksm(x+1,mod-2)%mod;
}
#undef int
int main()
{
    #define int register long long
    #define ll long long
    scanf("%lld%lld",&n,&task);
    get_Jc();
    get_Inv();
    if(task==0)
    {
        for(int i=0;i<=n;i+=2)
            ans=(ans+C(i,n)%mod*C(i>>1,i)%mod*C((n-i)>>1,n-i)%mod)%mod;
    }
    else    if(task==1)
        ans=Catalan(n>>1)%mod;
    else    if(task==2)
    {
        n>>=1;
        f[0]=1;
        f[1]=4;
        for(int i=2;i<=n;i++)
            for(int j=1;j<=i;j++)
                f[i]=(f[i]+4*f[i-j]%mod*Catalan(j-1)%mod)%mod;
        ans=f[n]%mod;
    }
    else
    {
        for(int i=0;i<=n;i+=2)
            ans=(ans+C(i,n)*Catalan(i>>1)%mod*Catalan((n-i)>>1)%mod)%mod;
    }
    printf("%lld",ans%mod);
    return 0;
}