【loli的胡策】NOIP训练10.5（组合数学+catalan数讲解）
吐槽：
T1：以后考试要看准范围啊！只开了1e5炸了空间！！！
T2：为什么不含ss的操作还会T啊，一删了那个操作就多分？评测机你给我出来？
但这样依然避免不了被题解学弟踩
T3:
【题目描述】
出个题就好了.这就是出题人没有写题目背景的原因.
你在平面直角坐标系上.你一开始位于(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取模
这还是太简单了,所以你给能够到达的格点加上了一些限制.一共有三种限制,加上没有限制的情况,一共有四种情况,用0,1,2,3标号:
0.没有任何限制,可以到达坐标系上所有的点,即能到达的点集为{(x,y)|x,y为整数}
1.只允许到达x轴非负半轴上的点.即能到达的点集为{(x,y)|x>=0,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.
对于typ=1 ——– {(x,y)|x>=0,y=0}
答案为catalan数.可以运用catalan(n)=C(2n,n)/(n+1)但是因为模数的关系，你并不能直接求C然后除，可以在求模数的时候除？相当麻烦，所以我推荐用Catalan(n)=c(2n,n)-c(2n,n-1)
原理：模拟出入栈
对于typ=0 ——– {(x,y)|x,y为整数}
枚举横向移动了多少步.横向移动i步时(i为偶),方案数为C(n,i)*C(i,i/2)*C((n-i),(n-i)/2)
原理：横向选择i步移动，i步中有一半正向移动，剩下纵向的n-i步中，一半正向移动
为什么这里可以直接运用C(i,i/2)而typ=1不行呢？因为typ=1你必须保证任意前缀入栈不少于出栈，不然就走到负半轴啦，而这里可以随意走，反正殊途同归
对于typ=2 ——– {(x,y)|x=0 || y=0}
f[i]表示走了i步回到原点的方案数,枚举第一次回到原点时走过的步数j(j为偶),则此时方案数为f[i-j]*catalan(j/2-1),复杂度为O(n^2)所以最大范围只出到1000.
f[j]表示第j步第一次回到原点，之后可能有多次再次回原点（f[i-j]）， 在计算这j步时，我们必须保证j步中不回原点，所以catalan(j/2-1) 这个-1就是保证栈不为空 （移动=出入栈）
对于typ=3 ——– {(x,y)|x>=0,y>=0}
枚举横向移动了多少步.横向移动i步时(i是偶),方案数为C(n,i)*catalan(i/2)*catalan((n-i)/2)
选择n步中的i步横向移动，其中一半的步数正向移动， 剩下纵向移动的步数中，也有一半的步数正向移动 Catalan保证是在第一象限内移动（任意前缀入栈不少于出栈）
这里运用线性求逆元，也可以用费马小定理
代码：
#include<cstdio>
#define LL long long
using namespace std;
const int N=200009;
const int mod=1e9+7;
using namespace std;
LL mul[N],inv[N],n,ty,ans,f[N];
void init()
{
int i;mul[0]=mul[1]=1;
for (i=2;i<=2e5;i++) mul[i]=mul[i-1]*i%mod;
inv[0]=inv[1]=1;
for (i=2;i<=2e5;i++) inv[i]=(mod-(mod/i))*inv[mod%i]%mod;
for (i=2;i<=2e5;i++) inv[i]=inv[i]*inv[i-1]%mod;
}
LL C(LL n,LL m)
{
return mul[n]*inv[m]%mod*inv[n-m]%mod;
}
LL Catalan(LL n,LL m)
{
return (C(n,m)-C(n,m-1)+mod)%mod;
}
void work0()
{
LL ans=0;
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;
printf("%lld",ans);
}
void work2()
{
n/=2; f[0]=1; f[1]=4;
for(int i=2;i<=n;i++)//走了i步回到原点
for(int j=1;j<=i;j++)//走了j步第一次回到原点
f[i]=(f[i]+f[i-j]*4*Catalan((j-1)*2,j-1)%mod)%mod;
//f[i-j]*4表示第一次到达原点之后可以从四个方向乱晃
//Catalan用j-1表示这j-1步不要换方向（换了方向就路过原点了！），在第j步走到原点
printf("%lld",f[n]);
}
void work3()
{
LL ans=0;
for (int i=0;i<=n;i+=2)
ans=(ans+C(n,i)*Catalan(i,i/2)%mod*Catalan(n-i,(n-i)/2))%mod;
printf("%lld",ans);
}
int main()
{
freopen("problem.in","r",stdin);
freopen("problem.out","w",stdout);
scanf("%d%d",&n,&ty);
init();
switch(ty)
{
case 0:work0();break;
case 1:printf("%lld",Catalan(n,n/2));break;
case 2:work2();break;
case 3:work3();break;
}
}普及向：
卡特兰数：
这是一串神奇的数字：
(1), 1, 2, 5, 14,
42, 132, 429, 1430, 4862,
16796, 58786, 208012, 742900, 2674440…….
令h(0)=1,h(1)=1，catalan数满足递推式：
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + … + h(n-1)*h(0) (n>=2)
例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2
h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5
另类递推式：
h(n)=h(n-1)*(4*n-2)/(n+1);
递推关系的解为：
h(n)=C(2n,n)/(n+1) (n=0,1,2,…)
递推关系的另类解为：
h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,…)
这个东西除了解这道题有什么用呢
括号化
矩阵连乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？h(n)
出栈次序
一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列？h(n)
凸多边形三角划分
在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干个三角形。任务是键盘上输入凸多边形的边数n，求不同划分的方案数f（n）。比如当n=6时，f（6）=14。
给定节点组成二叉搜索树
给定N个节点，能构成多少种不同的二叉搜索树？h（n）（这个公式的下标是从h(0)=1开始的）