Problem：　　

　　n个人（偶数）排队，排两行，每一行的身高依次递增，且第二行的人的身高大于对应的第一行的人，问有多少种方案。mod 1e9+9

Solution：

　　这道题由1,2,5,14 应该想到Catalan数，但是我却花了两个小时去找递推式。

　　首先 Catalan数 ：

　　基本规律：1,2,5,14,42,132，..........

典型例题：

　　1、多边形分割。一个多边形分为若干个三角形有多少种分法。

　　　　C(n)=∑(i=2...n-1)C(i)*C(n-i+1)

　　2、排队问题：转化为n个人在第一行为0，第二行为1，则n个人的序列中，在1前面的所有0,1中，0的个数一定要大于1。

　　　　　　　　见：http://blog.csdn.net/vast_sea/article/details/8173362      。类似于下一个问题。

　　3、出入栈问题：问出入栈的方案数。

　　　　与上一个问题相似，转换为0 为入栈，1为出栈，则合法的出入栈方案有多少？

　　4,、括号匹配问题：n对括号有多少种匹配方式？类似于出入栈。

　　5、二叉树问题：n个节点的二叉树有多少种形式？

　　　　　用T(i,j)表示 左节点 i 个，右节点 j 个。则根节点一定有一个，所以形式数为：T(0,n-1),T(1,n-2),T(2,n-3)....

　　　　　f[n]=f[0]*f[n-1]+f[1]*f[n-2]+.....+f[n]*f[0] 

其次，Catalan数问题解决后，我们用C(n)=C(n-1)*(4*n-2)/(n-1)求解（不要问我哪里来的，我也不知道）。然后就会发现一个问题：

　　A/BmodP 在数据大的情况下可能会出错，而A/BmodP肯定不等于AmodP/BmodP,这时就需要用到 逆元 了。

逆元：

　　ax≡1(mod P)    ->  ax mod P=1 mod P = 1  ->    b/a*(ax) mod P == b/a mod P==b*x mod P

即 x 为a mod P的逆元。

求逆元的方式：

　　1、扩展欧几里得：

　　　　因为ax≡1(mod P)，所以ax-1=nP,即ax-1为P的倍数。所以移项得：ax-nP=1。然后由扩展欧几里得算法推出x的解。

　　　　扩展欧几里得算法推导：

　　　　　　设 ax1+by1=gcd(a,b)    ∵gcd(a,b)=gcd(b,a%b)   ∴bx2+(a%b)y2=ax1+by1

　　　　　　∵a%b=a-(a/b)*b   ∴bx2+ay2-(a/b)*b*y2=ax1+by1

　　　　　　根据恒等定理：x1=y2;  y1=x2-(a/b)*y2

　　　　这样我们可以用递归求解，直到 b==0，x=1，y=0。递归x2,y2求x1,y1.

　代码：

void gcd(ll a,ll b,ll &d,ll &x,ll &y){    if (b==0){        d=1;x=1;y=0;    }    else {        gcd(b,a%b,d,y,x);y-=x*(a/b);//注意这里的y，x的区别，在递归的过程中，已经交换了x和y，所以为y-=x*(a/b);    }}

　　2、费马小定理：

　　　　a^(p-1)≡1(mod P)

　　　　则： a*a^(p-2)≡1(mod P)   

　　　　逆元：ax≡1(mod P)，则x为a^(p-2)，x为a mod P的逆元。可以由快速幂求得，但是如果数据大就太慢。

　代码：

ll ksm(ll x)//快速幂 {    ll tmp=x,t=1,k=P-2;    while (k>0){        if (k%2) t=(t*tmp)%P;        k=k>>1;        tmp=(tmp*tmp)%P;    }    return t;}void pre(){    inv[1]=1;    for (int i=2;i<=N;i++)//费马小定理求 逆       inv[i]=ksm(i);}

　　这样，就可以A 了这道题。顺带复习了很多数论和递推知识。

代码：

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define P 1000000009 6 #define N 1000000 7 #define ll long long 8 using namespace std; 9 int t;10 ll cat[N];11 void gcd(ll a,ll b,ll &d,ll &x,ll &y)12 {13     if (b==0){14         d=1;x=1;y=0;15     }16     else {17         gcd(b,a%b,d,y,x);y-=x*(a/b);18     }19 }20 ll inv(ll q,ll w)21 {22     ll d,x,y;23     gcd(q,w,d,x,y);24     return d==1?(x+w)%w:-1;    25 }26 void pre()27 {28     cat[1]=1;29     for (int i=2;i<=N;i++)30       cat[i]=cat[i-1]*(4*i-2)%P*inv(i+1,P)%P;31 }32 int main()33 {34     freopen("a.in","r",stdin);35     freopen("a.out","w",stdout);36     pre();37     cin>>t;38     while (t)39     {40         int n;41         scanf("%d",&n);42         printf("%I64d\n",cat[n/2]);43         t--;44     }45     return 0;46 }

【64测试20161112】【Catalan数】【数论】【扩展欧几里得】【逆】