数据结构与算法

卡特兰数

求解 

1
2
3
4
5
6
7

constexpr auto catlan(int n) -> ll {
	if (n == 0) return 1;
	ll res = 1;
	for (int i = 0; i < n; ++i)
		res = res * (4 * i - 2) / (i + 1);
	return res;
}

用途

  1. 树 の种类数