小红的二叉树【牛客tracker 每日一题】

小红的二叉树

时间限制：1秒 空间限制：1024M

知识点：数论

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

小红想知道，深度为n nn的满二叉树[1][1]有多少条长度为2 22的简单路径[ 2 ] [2][2]？由于答案可能很大，请将答案对( 10 9 + 7 ) (10^9+7)(109+7)取模后输出。
在本题中，两条简单路径所包含的点集不同时，被视为不同的。例如，路径u − v u−vu−v与路径v − u v−uv−u被视为相同的，因为它们均包含点u uu与点v vv。

一棵深度为h hh的满二叉树[ 1 ] [1][1]由恰好2 h − 1 2h−12h−1个节点组成，每一个节点要么是叶子节点，要么有2 22个儿子，并且全部叶子节点的深度均为h hh。
简单路径[ 2 ] [2][2]是指这样一条路径，其经过的顶点和边互不相同。

输入描述：

在一行上输入一个正整数n ( 1 ≦ n ≦ 10 4 ) n(1≦n≦10^4)n(1≦n≦104)代表满二叉树的深度。

输出描述：

输出一个整数，代表深度为n nn的满二叉树中，长度为2 22的简单路径的数量。由于答案可能很大，请将答案对( 10 9 + 7 ) (10^9+7)(109+7)取模后输出。

示例1

输入：

1

输出：

0

说明：

在这个样例中，深度为1 11的满二叉树只有1 11个节点，所以没有长度为2 22的简单路径。

示例2

输入：

3

输出：

7

说明：

在这个样例中，所给出的满二叉树如下图所示：

解题思路

本题通过递推公式+满二叉树结构分析求解长度为2 22的简单路径数，核心是推导路径数的递推规律：深度为1 11的满二叉树仅1 11个节点，路径数为0 00；深度为2 22时仅1 11条路径；深度≥ 3 ≥3≥3时，设r e s resres为当前层可产生新路径的节点数（初始为2 22），每增加一层，新增路径数为r e s × 3 res×3res×3（满二叉树每个中间节点可衍生3 33条新的长度为2的路径），总路径数a n s ansans累加该值，同时r e s resres翻倍（满二叉树每层节点数呈2 22倍增长）；遍历计算至目标深度n nn，所有操作对1 e 9 + 7 1e9+71e9+7取模。该递推方法时间复杂度为O ( n ) O(n)O(n)，无冗余计算，完美适配n ≤ 1 e 4 n≤1e4n≤1e4的规模，精准统计深度为n nn的满二叉树中长度为2 22的简单路径总数。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e6+10;intmain(){ll n;cin>>n;if(n==1)cout<<0;elseif(n==2)cout<<1;else{ll res=2,ans=1;for(inti=3;i<=n;i++){ans=(ans+res*3)%p;res=(res*2)%p;}cout<<ans%p;}return0;}