【CSP-S膜你考】最近公共祖先 To Be Continued

Problem A. 最近公共祖先 (commonants.c/cpp/pas)

$notes$

Input file: commonants.in
Output file: commonants.out
Time Limit : 0.5 seconds
Memory Limit: 512 megabytes

题面

最近公共祖先$\text{(Lowest Common Ancestor,LCA)}$是指在一个树中同时拥有给定的两个点作为后
代的最深的节点。
为了学习最近公共祖先，你得到了一个层数为$n+1$的满二叉树，其中根节点的深度为$0$，其他节点的深度为父节点的深度$+1$。你需要求出二叉树上所有点对 $\texttt{(i,j)}$,（$i$,$j$可以相等，也可以$i > j$）的最近公共祖先的深度之和对$10^9+7$取模后的结果。

输入格式

一行一个整数$n$。

输出格式

一行一个整数表示所有点对 $\texttt{(i,j)}$,（$i$,$j$可以相等，也可以$i > j$）的最近公共祖先的深度之和对$10^9+7$取模后的结果。

样例

input#1
2

input#2
19260817

output#1
22

output#2
108973412

样例解释

样例$1$解释：

原文链接:https://www.cnblogs.com/poi-bolg-poi/p/11661517.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有