hdu--6121--Build a tree

小鱼儿 2022-06-10 10:06 124阅读 0赞

# Build a tree #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)  
Total Submission(s): 535    Accepted Submission(s): 167**

Problem Description

HazelFan wants to build a rooted tree. The tree has   n nodes labeled   0 to   n−1, and the father of the node labeled   i is the node labeled   ⌊i−1k⌋. HazelFan wonders the size of every subtree, and you just need to tell him the XOR value of these answers.

Input

The first line contains a positive integer   T(1≤T≤5), denoting the number of test cases.  
For each test case:  
A single line contains two positive integers   n,k(1≤n,k≤1018).

Output

For each test case:  
A single line contains a nonnegative integer, denoting the answer.

Sample Input

2
    5 2
    5 3

Sample Output

7
    6

题目大意：

题目给出节点数为n的满k叉树，求出这棵满k叉树所有子树节点个数的异或总和。

解题思路：

对于所有的子树，可能会存在一棵不是满k叉树，就是编号为n-1的节点所在的那棵树，就把这棵子树的根节点作为

分界点，由满k叉树的性质知道，这个分界点的左边为满k叉树，而这个点的右边是比左边少一层的满k叉树。由此

可以得出一个结论，在每一层有三种情况，满二叉树，不满的二叉树，以及少一层的满k叉树。从叶子节点开始向上递归处理，把这三种情况分开处理。满的k叉树的节点个数比较容易得出，对于那个不满的，可以用右边的那种情况，加上多出来的节点数。需要注意的是k为1的情况要进行特殊处理。

更多细节性的东西，代码中有注释：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 68 
 69 
 70 
 71 
 72 
 73 
 74 
 75 
 76 
 77 
 78 
 79 
 80 
 81 
 82 
 83 
 84 
 85 
 86 
 87 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&nbsp;&lt;bits/stdc++.h&gt; 
 
 #define&nbsp;ll&nbsp; 
 long&nbsp; 
 long 
 
 #define&nbsp;maxn&nbsp; 
 105 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 ll&nbsp;n,&nbsp;k; 
 ll&nbsp;num[maxn]; 
 
 ll&nbsp;power(ll&nbsp;a,&nbsp;ll&nbsp;n) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///快速幂 &nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;ans&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(n) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(n&nbsp;&amp;&nbsp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;*=&nbsp;a; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a&nbsp;*=&nbsp;a; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n&nbsp;&gt;&gt;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp;ans; 
 } 
 
 
 void&nbsp;init(ll&nbsp;k,&nbsp;ll&nbsp;depth) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///预处理出完全k叉树前i层节点个数和 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;=&nbsp;depth;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;num[i]&nbsp;=&nbsp;(power(k,&nbsp;i)&nbsp;-&nbsp; 
 1)&nbsp;/&nbsp;(k&nbsp;-&nbsp; 
 1);&nbsp; 
 ///k^0+k^1+k^2....k^i，（每一层为k^i）; } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;t; 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d",&nbsp;&amp;t); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(t--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;ans; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%lld%lld",&nbsp;&amp;n,&nbsp;&amp;k); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(k&nbsp;==&nbsp; 
 1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///变为为链表 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;temp&nbsp;=&nbsp;n&nbsp;%&nbsp; 
 4; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(temp&nbsp;==&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;=&nbsp;n; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else&nbsp; 
 if(temp&nbsp;==&nbsp; 
 1) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else&nbsp; 
 if(temp&nbsp;==&nbsp; 
 2) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;=&nbsp;n&nbsp;+&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 else 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;=&nbsp; 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%I64d\n",&nbsp;ans); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 continue; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;depth&nbsp;=&nbsp; 
 1;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///求出树的高度 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;res&nbsp;=&nbsp;n&nbsp;-&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 while(res&nbsp;&gt;&nbsp; 
 0) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;res&nbsp;=&nbsp;(res&nbsp;-&nbsp; 
 1)&nbsp;/&nbsp;k;&nbsp;&nbsp; 
 ///求父节点， &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;depth++;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///高度加一 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;init(k,&nbsp;depth); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;=&nbsp;n;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///根节点为0的子树 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if((n&nbsp;-&nbsp;num[depth&nbsp;-&nbsp; 
 1])&nbsp;&amp;&nbsp; 
 1)&nbsp; 
 ///异或可以相互抵消 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;^=&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;depth--; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;pos&nbsp;=&nbsp;(n&nbsp;-&nbsp; 
 1&nbsp;-&nbsp; 
 1)&nbsp;/&nbsp;k;&nbsp; 
 ///临界点在以编号为pos节点为根的子树上 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;now&nbsp;=&nbsp; 
 2;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///当前是从下往上第几层 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 while(depth&nbsp;&gt;&nbsp; 
 1)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///depth等于1，即变为以0为根节点的子树时，结束递归 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;left&nbsp;=&nbsp;num[depth&nbsp;-&nbsp; 
 1];&nbsp; 
 ///当前层最左边节点的编号 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;right&nbsp;=&nbsp;num[depth]&nbsp;-&nbsp; 
 1;&nbsp; 
 ///当前层最右边节点的编号 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;temp1&nbsp;=&nbsp;num[now];&nbsp;&nbsp;&nbsp; 
 ///当前层满k叉树&nbsp;&nbsp;子树节点个数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;temp2&nbsp;=&nbsp;num[now&nbsp;-&nbsp; 
 1];&nbsp; 
 ///当前层满k叉树&nbsp;&nbsp;层数减1后&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;子树节点个数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if((pos&nbsp;-&nbsp;left)&nbsp;&amp;&nbsp; 
 1)&nbsp;&nbsp;&nbsp; 
 ///临界点左边满k叉树的个数为奇数，那么结果异或上节点个数，否则异或相互抵消，不计 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;^=&nbsp;temp1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if((right&nbsp;-&nbsp;pos)&nbsp;&amp;&nbsp; 
 1)&nbsp;&nbsp; 
 ///同理 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;^=&nbsp;temp2; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ll&nbsp;cnt&nbsp;=&nbsp;pos; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 while(cnt&nbsp;&lt;=&nbsp;(n&nbsp;-&nbsp; 
 1&nbsp;-&nbsp; 
 1)&nbsp;/&nbsp;k)&nbsp; 
 ///由于cnt*k+1&lt;=n-1,左边会爆long&nbsp;long,故转化为除法。 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cnt&nbsp;=&nbsp;cnt&nbsp;*&nbsp;k&nbsp;+&nbsp; 
 1;&nbsp; 
 ///求出这个不满k叉树最左边的子叶编号，则n-cnt就是这个不满k叉树的子叶个数，拿右边少一层的满k叉树节点个数加上n-cnt就是这个不满k叉树的节点数 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans&nbsp;^=&nbsp;num[now&nbsp;-&nbsp; 
 1]&nbsp;+&nbsp;n&nbsp;-&nbsp;cnt;&nbsp; 
 ///临界点的子树特殊处理 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;now++; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;depth--; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;pos&nbsp;=&nbsp;(pos&nbsp;-&nbsp; 
 1)&nbsp;/&nbsp;k;&nbsp; 
 ///界限向上推一个 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "%I64d\n",&nbsp;ans); 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>