小白月赛D题题解

D题题解：

我们知道一个树的满二叉树节点数为1,3,7，...

节点数是2的n次幂-1

现在问题是给出一棵高度为n的树，如何能快速求出这棵树种每种层数的树的个数

因此我们可以先预处理处2的n次幂都是多少，再开一个二维数组cnt[i][j]，用来记录高度为i的树在总高度为j的树中有多少个小分支，

但是这样还不行，因为有下面这种情况：

此时最下面一层还能对应它们各自的子树，我们发现2的整数个节点的子树个数为2^n-1个

所以可以对下面一层子树进行递归处理，直到最后剩下的节点小于2个，不再能构成子树为止

这是本人第一次写题解，当时做出来这道题很兴奋，希望大家也能越来越棒！！！

下面是这道题的代码

#include <iostream>

int main() {
    std::cout << "Hello World!";
    return 0;
}
```#include<iostream>
using namespace std;
#include<cstring>

const int N = 1e6+20, mod = 1e9+7;

typedef long long LL;
LL cnt[65][65],num[65];

void solve(){
    LL n;
    cin>>n;
    
    LL res=n%mod;
    int t=0;
    LL temp=0;
  //计算这棵树最大有几层，并计算最下面一层节点个数
    for(int i=60;i>=0;i--) 
        if(n>=num[i]-1){
            t=i-1;
            temp=n-(num[i]-1);
            break;
        }
    
    for(int i=t;i>=1;i--){
        for(int j=t;j>=i;j--){
            res=(res+cnt[i][j])%mod;
        }
    }
    
  //对余下的节点个数进行递归处理，使得最后剩下的节点数<2不再能构成一棵子树
    while(temp>=2){
        for(int i=60;i>=1;i--){
            if(temp>=num[i]) {
                res=(res+num[i]-1)%mod;
                temp-=num[i];
                break;
            }
        }
    }
    cout<<res<<endl;
}

int main(){
    num[0]=1;
  //预处理2的整数次幂
    for(int i=1;i<=60;i++) {
        num[i]=num[i-1]*2;
    }
    
    for(int i=1;i<=60;i++) cnt[i][i]=1;
    
  //预处理每棵高度为i的子树在总高度为j的树中的个数
    for(int i=1;i<=60;i++){
        LL t=2;
        for(int j=i+1;j<=60;j++){
            cnt[i][j]+=t;
            t*=2;
        }
    }
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    
    return 0;
}