HDU 6121 Build a tree（完全K叉树）

http://acm.hdu.edu.cn/showproblem.php?pid=6121

题意：
给你一颗完全K叉树，求出每棵子树的节点个数的异或和。

思路：

首先需要了解一些关于完全K叉树或满K叉树的一些知识：

对于每棵子树，只有三种情况：

①是满K叉树  ②不是满K叉树  ③叶子节点

并且非满K叉树最多只有一个，所以只需要将它进行特殊处理，具体看代码吧，说不清楚。代码参考了http://blog.csdn.net/my_sunshine26/article/details/77200282。

当K=1时，树是链状的，需要打表找规律！

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,ll> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 ll n, k, ans;

 ll num[maxn];

 int depth;

 void init()

 {

     num[]=;

     for(int i=;i<=depth;i++)

     {

         num[i]=num[i-]+pow((long double)k,(long double)i-);  //因为pow默认是pow(int,int),没有对应long long的，所以我这儿用long double来代替了一下

     }                                                          //当然这里可以自己用快速幂来计算

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     int T;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%I64d%I64d",&n,&k);

         if(k==)                  //特判

         {

             ll tmp=n%;

             if(tmp==) ans=n;

             else if(tmp==) ans=;

             else if(tmp==) ans=n+;

             else ans=;

             printf("%I64d\n",ans);

             continue;

         }

         depth=;

         ll tmp=n-;

         //计算树的深度

         while(tmp>)

         {

             tmp=(tmp-)/k;

             depth++;

         }

         init(); //预处理前i层的节点个数

         ans=;

         ans^=(n-num[depth-])&; //先处理一下最后一层

         depth--;

         ll now=;  //当前从下往上第几层

         ll pos=(n--)/k;

         while(depth>)

         {

             ll left=num[depth-];  //当前层数最左边编号

             ll right=num[depth]-; //当前层数最右边编号

             ll tmp1=num[now];      //左边树大小

             ll tmp2=num[now-];    //右边树大小

             //奇数才有贡献

             if((pos-left)&)   ans^=tmp1;

             if((right-pos)&)  ans^=tmp2;

             ll cnt=pos;

             while(cnt<=(n--)/k)  cnt=cnt*k+;

             ans^=(num[now-]+n-cnt);  //单独处理临界点子树

             now++;

             depth--;

             pos=(pos-)/k;

         }

         printf("%I64d\n",ans);

     }

     return ;

 }