1.网格

转换模型,翻折容斥出解。

2.有趣的数列

抽象一下模型,把奇数项当作横坐标,偶数项当作纵坐标,就是从n*n矩阵左下角走到右上角并且每一步x<=y的方案数,发现是卡特兰数,关于gcd,可以线筛出质数,顺手处理每个数的最小质因子,从而快速得到每个数的唯一分解,从而约分。

3.树屋阶梯

把每放上一块后当前x的最大值和y的最大值想象成坐标点,这样是n*n矩阵从左下角走到右上角并且每一步x>=y的方案数,发现是卡特兰数,唯一分解约分高精乘。

4.数的计数

裸的prufer,注意各种特判即可。

5.明明的烦恼

还是prufer,答案是从n-2个位置中选择有度的所占的个数,之后取排列并乘上剩余位置的无度点次方(无度点在剩下的位置随便放)。还是注意特判。

总的来说卡特兰数重要的是转换各种模型,例如入栈出栈,1-1序列,括号匹配等等。

prufer最重要的不是他本身是,不符合的情况。

05-29 01:31