題(problem)(詳解10.5hu測T3：Catalan）

@liu_runda

【題目描述】

出個題就好了.這就是出題人沒有寫題目背景的原因.

你在平面直角坐标系上.

你一開始位于(0,0).

每次可以在上/下/左/右四個方向中選一個走一步.

即:從(x,y)走到(x,y+1),(x,y-1),(x-1,y),(x+1,y)四個位置中的其中一個.

允許你走的步數已經确定為n.現在你想走n步之後回到(0,0).但這太簡單了.你希望知道有多少種不同的方案能夠使你在n步之後回到(0,0).當且僅當兩種方案至少有一步走的方向不同,這兩種方案被認為是不同的.

答案可能很大是以隻需要輸出答案對10^9+7取模後的結果.(10^9+7=1000000007,1和7之間有8個0)

這還是太簡單了,是以你給能夠到達的格點加上了一些限制.一共有三種限制,加上沒有限制的情況,一共有四種情況,用0,1,2,3标号:

0.沒有任何限制,可以到達坐标系上所有的點,即能到達的點集為{(x,y)|x,y為整數}

1. 隻允許到達x軸非負半軸上的點.即能到達的點集為{(x,y)|x為非負數,y=0}

2. 隻允許到達坐标軸上的點.即能到達的點集為{(x,y)|x=0或y=0}

3. 隻允許到達x軸非負半軸上的點,y軸非負半軸上的點以及第1象限的點.即能到達的點集為{(x,y)|x>=0,y>=0}

【輸入格式】

一行兩個整數(空格隔開)n和typ,分别表示你必須恰好走的步數和限制的種類.typ的含義見【題目描述】.

【輸出格式】

一行一個整數ans,表示不同的方案數對10^9+7取模後的結果.

【樣例輸入0】

100 0

【樣例輸出0】

383726909

【樣例輸入1】

100 1

【樣例輸出1】

265470434

【樣例輸入2】

100 2

【樣例輸出2】

376611634

【樣例輸入3】

100 3

【樣例輸出3】

627595255

【資料範圍】

10%的資料,typ=0,n<=100

10%的資料,typ=0,n<=1000

5%的資料, typ=0,n<=100000

10%的資料,typ=1,n<=100

10%的資料,typ=1,n<=1000

5%的資料, typ=1,n<=100000

10%的資料,typ=2,n<=100

15%的資料,typ=2,n<=1000

10%的資料,typ=3,n<=100

10%的資料,typ=3,n<=1000

5%的資料, typ=3,n<=100000

以上11部分資料沒有交集.

100%的資料,保證n為偶數,2<=n<=100000,0<=typ<=3.

分析：

考場上的dp做法詳見hu測10.5

正解：

四合一Catalan應用

first.typ=1

裸的Catalan

模拟出入棧

second.typ=0

對于typ=0的資料

枚舉橫向移動了多少步

橫向移動i步時(為了存在合法解,i必須是偶數)

方案數為C(n,i)*C(i,i/2)*C((n-i),(n-i)/2)

橫向選擇i步移動，i步中有一半正向移動，剩下縱向的n-i步中，一半正向移動

third.typ=2

f[i]表示走了i步回到原點的方案數

（中途可能回到過原點多次）

枚舉第一次回到原點時走過的步數j(為了存在合法解,j為偶數)

則此時方案數為f[i-j]*catalan(j/2-1)

解釋：

第j步第一次回到原點，之後可能有多次再次回原點（f[i-j]），

在計算這j步時，我們必須保證j步中不回原點，是以catalan(j/2-1)

這個-1就是保證棧不為空

（在我們眼裡，移動就像出入棧）

最後答案需要*4

複雜度為O(n^2)是以最大範圍隻出到1000

fourth.typ=3

枚舉橫向移動了多少步

橫向移動i步時(為了存在合法解,i必須是偶數)

方案數為C(n,i)*catalan(i/2)*catalan((n-i)/2)

選擇n步中的i步橫向移動，其中一半的步數正向移動，

剩下縱向移動的步數中，也有一半的步數正向移動

Catalan保證是在第一象限内移動（任意字首入棧不少于出棧）

//這裡寫代碼片
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long

using namespace std;

const ll mod=;
const int N=;
int n,typ;
ll inv[N],jc[N],f[]; 

ll KSM(ll a,int b)
{
    a%=mod;
    ll t=;
    while (b)
    {
        if (b&) 
           t=(t%mod*a%mod)%mod;
        b>>=;
        a=(a%mod*a%mod)%mod;
    }
    return t%mod;
}

void cl()
{
    jc[]=; jc[]=;
    for (int i=;i<N;i++) jc[i]=(jc[i-]%mod*(ll)i%mod)%mod;
    inv[]=; inv[]=;
    for (int i=;i<N;i++) inv[i]=((mod-mod/i)%mod*inv[mod%i]%mod)%mod;
    for (int i=;i<N;i++) inv[i]=(inv[i]*(ll)inv[i-])%mod;  //階乘的逆元 
}

ll C(int n,int m)
{
    if (n<m) return ;
    if (m==) return ;
    return (jc[n]%mod*inv[m]%mod*inv[n-m]%mod)%mod;
}

ll Catalan(int x)  //公式求法 
{
    return C(*x,x)%mod*KSM((ll)(x+),mod-)%mod;   //費馬小定理求逆元 
}

int main()
{
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    scanf("%d%d",&n,&typ);
    cl();
    if (typ==)
    {
        printf("%lld",Catalan(n/));
    }
    else if (typ==)
    {
        ll ans=; 
        for (int i=;i<=n;i+=)   //為了能回到原點，枚舉的橫向步數一定是偶數 
            ans=(ans+C(n,i)%mod*C(i,i/)%mod*C(n-i,(n-i)/)%mod)%mod;
        printf("%lld",ans%mod);
    }
    else if (typ==)
    {
        n/=;  //友善dp 
        f[]=;
        f[]=;
        for (int i=;i<=n;i++)   //枚舉總步數 
            for (int j=;j<=i;j++)   //枚舉第一次到達原點的步數
                f[i]=(f[i]%mod+f[i-j]%mod*4*Catalan(j-)%mod)%mod;
        printf("%lld",f[n]%mod);
    }
    else
    {
        ll ans=;
        for (int i=;i<=n;i+=)
            ans=(ans+C(n,i)%mod*Catalan(i/)%mod*Catalan((n-i)/)%mod)%mod;
        printf("%lld",ans);
    }
    return ;
}