2026.2.10 小红的二叉树 树+排列组合

树的形状+排列组合
小红的二叉树
这个题其实是一个简单的排列组合吧。
题目要求是找到一个线段长度为2的，长度也2的线段是由三个点组成的。
所以我们只需要确定了中间那个点，在他的周围节点里面选两个就可以和自己一共组成三个点。
因为这是一个完全二叉树，所以可以发现如下规律：
只考虑中间节点，
当点为编号为一的点的时候，它只能和两个儿子字节点组成线段。
如果是叶子结点的话，则不能作为中间节点。
如果不是叶子节点，也不是编号为1的点的话，那么就可以和周围的点组成线段，而且周围的点，根据树的形状肯定是三个的。（也就是在三个里面选两个，对答案贡献三种情况。）

再想一下特判，当只有一个节点的时候答案为0；当只有两层的时候答案为一。
剩下的就可以总结出公式：
一共有多少个节点（2∧h-1），需要减去的叶子节点数和编号为1的节点（2∧(h-1)+1），最后再加上编号为1的节点会贡献一个。

注意对答案取模这个步骤可以写成ans=(ans%mod+mod)%mod; 因为负数对mod取余也是负的，一个数对mod取余后的范围是-（mod-1） ~ mod-1所以两个之差的最小值是-2*mod+2

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int mod = 1e9+7;
int qpow(int a,int b)
{if(b == 0)return 1;int res = 1;while(b){if(b&1) res *= a;a *= a;b >>= 1;res = (res+mod)%mod,a = (a+mod)%mod;}return res;
}
signed main()
{int h;cin>>h;if(h == 1){cout<<0<<endl;return 0;}else if(h == 2){cout<<1<<endl;return 0;}int ans = (qpow(2,h)-qpow(2,h-1)-2)*3+1;
//     cout<<qpow(2,h)<<" "<<qpow(2,h-1)<<endl;ans=(ans%mod+mod)%mod;cout<<ans<<endl;return 0;
}