| 题目名称 | 2425. [HZOI 2016]简单的AVL树 |
|---|---|
| 输入输出 | AVL.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Hzoi_
于2016-08-10加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：17， 提交：42， 通过率：40.48% | ||||
 yymxw |
100 | 0.000 s | 0.00 MiB | C++ |
 Hallmeow |
100 | 0.000 s | 0.00 MiB | C++ |
 HolyK |
100 | 0.000 s | 0.00 MiB | C++ |
 ┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
|
yymxw |
100 | 0.002 s | 0.31 MiB | C++ |
 HeHe |
100 | 0.002 s | 0.31 MiB | C++ |
 再见 |
100 | 0.003 s | 0.29 MiB | C++ |
 AntiLeaf |
100 | 0.003 s | 0.31 MiB | C++ |
|
梦那边的美好ET |
100 | 0.003 s | 0.31 MiB | C++ |
 Ninaye |
100 | 0.003 s | 0.32 MiB | C++ |
| 关于 简单的AVL树 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
longlong！！
| ||||
|
裸的矩阵快速幂。。。。\[
\left( \begin{array}{l} f(n - 1) & f(n) & 1 \\ \end{array}\right) \quad * \quad \left(\begin{array}{l} 0 & 1 & 0\\ 1 & 1 & 0\\ 0 & 1 & 1\\ \end{array}\right) \quad = \quad \left(\begin{array}{l} f(n) & f(n - 1) + f(n) + 1 & 1 \end{array}\right) \] 第一次交忘加上freopen了。。。。。 | ||||
|
回复 @2018YaLi稳 :
讲道理不是开3*3的矩阵就可以了吗 Ninaye
2017-08-09 10:12
5楼
| ||||
|
抱歉拉低了正确率，矩阵开到100*100过了。于是认为越界，找了半天没找出问题。最后发现有个地方没打初始化0.。。。。。
可能是100*100的数组，系统开到了堆里面，而太小的话就在栈里面了。。。。 再见
2017-02-26 11:59
4楼
| ||||
|
不要逼我再用“简单的SBT”像秒你“简单的Treap”一样秒你“简单的AVL”
 _Itachi
2016-08-11 19:59
3楼
| ||||
|
mark
 YGOI_真神名曰驴蛋蛋
2016-08-11 19:50
2楼
| ||||
 Hzoi_
2016-08-10 21:37
1楼
| ||||
【题目描述】
AVL树是一种平衡二叉搜索树，除二叉搜索树的基本性质外，AVL树还满足一个性质：
每个节点的左子树与右子树的高度相差不超过1。
对高度的定义是：叶子节点的高度为1，其他节点的高度为左右子树高度的较大值+1。
现在，给定高度值h和模数p，你需要求出高度为h的AVL树最少包含的节点数模p的值。
【输入格式】
一行两个数，分别为h和p。
【输出格式】
一行一个数，表示答案。
【样例输入】
4 10007
【样例输出】
7
【样例解释】
一种符合要求的AVL树如图所示：
【数据范围】
对于30%的数据，有n<=$10^8$；
对于100%的数据，有n<=$10^{18}$，p<=$2*10^9$。
【来源】
HZOI 2016