题解 | #小红的二叉树#

考虑 $n=1$ ,直接输出 $0$

考虑 $n=2$ ,直接输出 $1$

考虑 $n\ge 3$ ,为了不重复计数，新增的路径数只可能是第三层多出来那些叶子结点

他们既可以向上两层（有多少个叶子结点，就有多少个这样的方案数，对应图中红色的路径）

又可以向上一层向下一层（显然有几个上一层有几个，就有多少个方案数，因为兄弟之间才能做一次这样的路径，对应图中蓝色路径）

满二叉树第 $i$ 层一共有 $2^{i-1}$ 个节点，于是每多一层，计数就多 $2^{i-1}$ 个红色路径，同时又多 $2^{i-2}$ 个蓝色路径

在实现上使用快速幂即可时间复杂度： $O(n\log n)$ ,预处理 $2^k$ 数组可以加速到 $O(n)$ 。

alt

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rrp(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=2e5+7;
const int M=1e9+7;
typedef long long ll;
typedef vector<int> vt;
int n;

ll fp(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=(ans*a)%M;
        a=(a*a)%M;
        b>>=1;
    }
    return ans;
}
void solve(){
   cin>>n;
   if(n==1){
        cout<<"0";
        return;
   }
   if(n==2){
        cout<<"1";
        return;
   }
   ll ans=1;
   rep(i,3,n){
       ans=(ans + fp(2,i-1))%M;
       ans=(ans + fp(2,i-2))%M;
   }
   cout<<ans<<"\n";
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}