卡特兰数
一般涉及卡特兰数的问题就两种：
1.问题可以转化为卡特兰数基本模型
2.dp推出了卡特兰数公式
卡特兰数基本模型
（1）有n个"("和n个")",求排列数，满足每一时刻“（”的数量>= “）”的数量，【合法栈问题】
（2）从原点（0,0）到点（n,n）的排列数，使得不越过x=y这条线
卡特兰数dp公式
本层是上一层首尾相乘的和
题目有下面特征之一的应该考虑卡特兰数
（1）有2n个物品
（2）计算过程出现了第i个*第n-1-i，即相乘两者下标和为n-1
卡特兰数基本公式
关于如何挑选公式：
mod是非素数时，n小，询问多时候用公式1，如洛谷p1722https://www.luogu.com.cn/problem/P1722，mod非素数逆元一般卡不存在
mod是非素数时，n大，询问少时候用公式3，计算所有因数的幂最后相乘，如洛谷p3200https://www.luogu.com.cn/problem/P3200
拓展模型计算公式
从（0,0）到（n,m）不经过x=y的方法数= 
或 
从（0,0）到（n,m）不穿过x=y的方法数=
或 
基本模型讲解
（1）可以n次左移一格和n次上移一格，求从原点（0,0）移动到点（n，n），并且途中保持x>y的方法数
即满足从（0,0）到（n，m）不经过红线的方法数（n>m）
合法排列=全部排列-非法排列
全部排列=C(2n,n)
非法可以这样想
第一步要么是到（1,0）要么到（0,1）
（0,1）到（n，m）一定穿过x==y，而（1,0）的非法数=（0,1）非法=（m+m-1，m-1）——因为对称 合法排列=（n+m，m）-2*（n+m-1，m-1）
或者（n+m-1，m）-（n+m-1，m-1）——因为第一步（0,1）已经非法，所以只有（1,0）合法，问题就到了从（1,0）出发的合法-（1,0）出发的非法
（2）如果是从（0,0）到（n，m）满足x>=y
不穿过红线的方法数
则就是不经过y==x+1（紫线）
原点关于紫线对称点是（-1,1），就相当于坐标轴左移，问题就转变成（0,0）到（n+1,m）不经过x== y 题目
几乎裸题：
dp推断
带点数论
拓展