数树【牛客tracker 每日一题】

数树时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述「开导」众所周知树是一种特殊的图。众所周知二导出子图是由该图顶点的一个子集和该图中两端均在该子集的所有边的集合组成的图。注1二叉树是有向图。注2有向图的导出子图还是有向图。小沙有n nn个节点他需要你构造出一棵有根二叉树使得二叉树的所有导出子图是一棵满二叉树的数目尽可能多。请问构造出来的有根二叉树的所有导出子图是一棵满二叉树的数目最多是多少你能帮帮不会数树的小沙吗输入描述第一行读入一个整数T TT代表多组样例。随后T TT行每行输入一个正整数n nn。保证有1 ≤ T ≤ 10 5 1 \le T \le 10^51≤T≤1051 ≤ n ≤ 10 18 1 \le n \le 10^{18}1≤n≤1018。输出描述对于每组样例输出一行整数代表答案。由于答案过大所以请输出答案对10 9 7 10^9 71097取模的值。示例 1输入10 1 2 3 4 5 6 7 8 9 10输出1 2 4 5 7 8 11 12 14 15说明对于7 77个节点的最优二叉树为1 / \ 2 3 / \ / \ 4 5 6 7其11 1111个导出子图为满二叉树的有即1 11整棵1 11节点1 , 2 , 3 1,2,31,2,32 22节点2 , 4 , 5 2,4,52,4,5与3 , 6 , 7 3,6,73,6,77 77单节点11 1111种。数据范围与提示1 ≤ T ≤ 10 5 1 \le T \le 10^51≤T≤1051 ≤ n ≤ 10 18 1 \le n \le 10^{18}1≤n≤1018答案对10 9 7 10^9 71097取模核心思路单节点本身是满二叉树故至少有n nn个要让满二叉树导出子图尽可能多应把树构造成尽量“满”的形态完全二叉树使得大小分别为1 , 3 , 7 , 15 , … 1, 3, 7, 15, \dots1,3,7,15,…即2 k − 1 2^k - 12k−1的满二叉树子树数量最多答案即为这些满二叉树子树的计数之和。由于n nn可到10 18 10^{18}1018需要按层递推/二分计算各规模的满二叉树个数再对10 9 7 10^9 71097取模。解题思路本题是构造最优二叉树 递推计数的数学问题。要求构造一棵有根二叉树使得其所有导出子图中是满二叉树完美二叉树的数量最多并输出这个最大数量对10 9 7 10^971097取模的结果。经过分析最优构造是一棵完全二叉树答案等于该完全二叉树中所有节点的“完美高度”之和。1. 问题等价转化满二叉树完美二叉树每个非叶子节点都有两个子节点且所有叶子节点在同一层。节点数必然为2 h − 1 2^h - 12h−1h hh为高度。导出子图选取原二叉树的一些节点保留两端都在该子集中的边形成的子图。若该子图是一棵满二叉树则它是一棵完美二叉树。最优构造为了让满二叉树导出子图尽可能多应将树构造成完全二叉树节点从上到下、从左到右依次排列。关键观察在完全二叉树中对于任意一个节点它可以作为根的满二叉树导出子图的数量等于从该节点开始向下连续的“满层”数即完美高度。例如一个叶子节点的完美高度为1 11只包含自己如果一个节点的左右子树都是满的且高度相同则它的完美高度为1 子树完美高度 1 \text{子树完美高度}1子树完美高度。因此总答案就是完全二叉树中所有节点的完美高度之和。2. 递推公式推导设完全二叉树的节点数为n nn。令m n 1 m n 1mn1。观察样例与代码答案r rr可以通过以下循环计算m n 1 r 0 while m 1: r m - 1 m m // 2例如n 7 n 7n7m 8 m 8m8r 7 3 1 11 r 7 3 1 11r73111。n 6 n 6n6m 7 m 7m7r 6 2 8 r 6 2 8r628。n 5 n 5n5m 6 m 6m6r 5 2 7 r 5 2 7r527。这个公式的直观意义在完全二叉树中每一层的节点数之和减去该层满二叉树的根数量累加起来恰好等于所有节点的完美高度之和。具体地m − 1 n m-1 nm−1n是总节点数然后m / 2 − 1 m/2 - 1m/2−1是上一层可以形成的满二叉树数量依此类推。3. 算法实现读入测试组数T TT。对于每组数据读入n nn。令m n 1 m n 1mn1初始化答案ans 0。当m 1 m 1m1时ans m - 1m 1即整除 2输出ans % (10^97)。4. 复杂度分析时间复杂度每次循环m mm减半循环次数为O ( log ⁡ n ) O(\log n)O(logn)。T ≤ 10 5 T \le 10^5T≤105n ≤ 10 18 n \le 10^{18}n≤1018总运算量约为10 5 × 60 6 × 10 6 10^5 \times 60 6 \times 10^6105×606×106非常快。空间复杂度O ( 1 ) O(1)O(1)仅使用几个变量。总结通过分析满二叉树导出子图的性质得出最优构造是完全二叉树且答案为所有节点的完美高度之和。利用m n 1 m n1mn1的不断右移累加可以快速计算该和。算法简洁高效完美处理n nn高达10 18 10^{18}1018的数据范围。代码简要说明使用long long存储n nn和中间变量m mm。循环条件m 1每次ans m - 1后m 1。最后输出ans % mod其中mod 1e97。输入输出使用cin/cout并关闭同步加速处理大量测试数据。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n;voidsolve(){cinn;ll r0;n;while(n1){rn-1;n1;}coutr%modendl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;cinT;while(T--)solve();return0;}