卡特兰式和快速幂
常用的应用场景:
1.括号匹配:有效的匹配方式,左括号数量不少于右括号数量。
2.计算具有几个节点的二叉搜索树。
3.路径问题:在一个n*n
的网格中,计算从左上角到右下角的路径数量,条件只能向右或者向下,不能穿对角线。
4.堆栈序列:计算n个元素有效的堆栈进出序列,有效序列指,进栈元素大于出栈元素。
5.凸多边形划分三角形:计算一个凸多边形可被划分成三角形数量。
举例:比如三对括号的有效匹配方式式5个。凸五边形划分成五种三角形。
卡兰特式 :H0:1 Hn = Hn-1*(4n-2)/n+1
洛谷P1044
题目
栈是计算机中经典的数据结构,简单的说,栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作,即 pop(从栈顶弹出一个元素)和 push(将一个元素进栈)。栈的重要性不言自明,任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时,想到了一个书上没有讲过的问题,而他自己无法给出答案,所以需要你的帮忙。你的程序将对给定的 n,计算并输出由操作数列 1,2,…,n 经过操作可能得到的输出序列的总数。
解析
可以看出这个是要给出有效情况。所以是卡特兰式操作
代码
1 |
|
快速幂
题目:给你三个整数a,b,p,求 a^bmodp。
输入格式:
1 |
|
输出格式:
1 |
|
题解
这个就是快速幂取模,快速幂的操作就是将幂指数变成二进制,然后一直对于超过的数一直取模就行了。
代码:
1 |
|
卡特兰式和快速幂
https://ljw030710.github.io/2024/01/30/卡特兰式和快速幂/