暑假考试题6：problem 题（Catlan + dp + 组合数）

题目：

分析：

若没有限制地在坐标轴上走，无论怎么走，走到的最远的点映射在横纵坐标上的数量是一定的，那么可以枚举这个数量，进行计算。

而规定只能走到非负半轴的限制，将1看做向右走，-1看做向左走，可以转换成任何时候的前缀和非0，这就对应着括号序。

0限制：坐标轴内都可以随便走，无论怎么走，横坐标走到的最远的点一定是确定的，且一定要走回来，纵坐标也一样。
选i步走横坐标，剩下的n-i步走纵坐标，那么i/2步必须走回去纵坐标也一样。

1限制：为了不走到负半轴，就必须每个时刻向右走的步数比向左走多，即为括号序。

2限制：定义f[i]为走了i步回到起点的方案数，因为必须走到起点才可以走纵坐标。
枚举j表示第一次走回到起点时走过的步数即之前都没有回到过所以是catlan( j/2 -1 )*4 （有四个方向）
-1原因：为了保证j是第一次走到起点，而没有在中途回到起点，就要保证第一个括号和最后一个括号匹配，那么第一个括号就是确定的，通过-1去掉一个括号再计算。

3限制：只能走一象限就相当于在op==0上加一个括号序，保证不走到其它象限。

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define N 100005
ll fac[N],inv[N],invfac[N],f[N];
int read()
{
    int x=0; int fl=1; char ch=getchar();
    while(ch>'9'||ch<'0') { if(ch=='-') fl=-1; ch=getchar(); }
    while(ch<='9'&&ch>='0') { x=x*10+ch-'0'; ch=getchar(); }
    return x*fl;
}
ll quick_pow(ll a,ll k)
{
    ll ans=1;
    while(k){
        if(k&1) ans=ans*a %mod;
        a=a*a%mod;
        k>>=1;
    }
    return ans;
}
ll catlan(int n)
{
    if(n<0) return 0;
    return fac[2*n]*invfac[n] %mod *invfac[n] %mod * inv[n+1] %mod;
}
ll C(int n,int m)
{
    return fac[n]*invfac[m] %mod *invfac[n-m] %mod ;
}
int main()
{
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    int n,op;
    n=read(); op=read();
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i %mod;
    invfac[n]=quick_pow(fac[n],mod-2);
    for(int i=n;i>=1;i--) invfac[i-1]= invfac[i]*i %mod;
    inv[1]=1;
    for(int i=2; i<=n; ++i)
      inv[i]=((mod-mod/i)*inv[mod%i]%mod+mod)%mod;
    ll ans=0;
    if(op==0){
        //坐标轴内都可以随便走 无论怎么走 横坐标走到的最远的点一定是确定的 且一定要走回来 纵坐标也一样
        //选i步走横坐标 剩下的n-i步走纵坐标 那么i/2步必须走回去 纵坐标也一样 
        for(int i=0;i<=n;i+=2) ans=( ans+ C(n,i)*C(i,i/2) %mod *C(n-i,(n-i)/2)%mod )%mod;
        printf("%lld
",ans);
    }
    else if(op==1)//为了不走到负半轴 就必须每个时刻向右走的步数比向左走多 即为括号序 
     printf("%lld
",catlan(n/2));
    else if(op==2){
    //定义f[i]为走了i步回到起点的方案数 因为必须走到起点才可以走纵坐标 
    //枚举j表示第一次走回到起点时走过的步数 即之前都没有回到过 所以是catlan(j/2-1)*4 有四个方向
    //-1原因： 
        f[0]=1;//记得初始化 
        for(int i=0;i<=n;i++)
         for(int j=0;j<=i;j+=2)
          f[i]=( f[i] + f[i-j]*catlan(j/2-1)*4 %mod ) %mod ;
        printf("%lld
",f[n]);
    }
    else if(op==3){
    //只能走一象限就相当于在op==0上加一个括号序 保证不走到其它象限 
        for(int i=0;i<=n;i+=2) ans=( ans+ C(n,i)*catlan(i/2) %mod *catlan((n-i)/2) %mod )%mod;
        printf("%lld
",ans);
    }
    return 0;
}
/*
100 1
100 2
*/

View Code