AcWing 1316. 有趣的数列    原题链接    中等

作者： 作者的头像   黄亦玫 ,  2020-10-28 21:57:20 ,  所有人可见 ,  阅读 492

2


1

分析一道题是不是卡特兰数的方法有两种

  • 从递推式的角度来看，如果f[n] = f[1] * f[n - 1] + f[2] * f[n - 2] .. 那么就是卡特兰数，比如求二叉树的个数
  • 挖掘一种性质：任意前缀中，某种东西一定不能少于等于另一种东西。
  • 本题的做法：由于模数不是个质数因此，只能用分解质因数+快速幂求解即可。

5 评论

用户头像
啥也不会hh   2022-04-05 08:12         踩      回复

为啥不用考虑这个性质啊？任意相邻的两项 a2i−1 与 a2i (1≤i≤n) 满足奇数项小于偶数项，即：a2i−1<a2i。

用户头像
RingweEH   2020-10-28 21:58         踩      回复

还有第2.5种，背百度百科上的典型案例然后自行推理（

用户头像
黄亦玫   2020-10-28 22:04         踩      回复

求链接

用户头像
RingweEH   2020-10-28 22:07    回复了 黄亦玫 的评论         踩      回复

？百度百科 中的应用部分；

OI-wiki

用户头像
黄亦玫   2020-10-29 08:33    回复了 RingweEH 的评论         踩      回复

好的谢谢QAQ