HazelFan wants to build a rooted tree. The tree has nn nodes labeled 0 to n−1, and the father of the node labeled i is the node labeled 

. HazelFan wonders the size of every subtree, and you just need to tell him the XOR value of these answers.

2

5 2

5 3

7

6

题意：画一下题目介绍的树，发现这是一个k叉树，那么题目要求所有子树大小的异或和。
思路：我们从序号为n的节点开始，往上求异或和。n计算到某一层时，对于处在n节点左边的节点（子树），它们是t+1层的满k叉树，在右边的节点（子树）是t层的满二叉树，
满二叉树的大小可以通过打表得到。根据异或计算的性质，大小相同的子树进行异或，有奇数个进行异或时结果为该子树的大小，偶数个时为0。
而对n位置节点的子树来说，不是满二叉树就是非满二叉树，而且在计算这个子树大小时一旦它在某一层是非满二叉树，接下来往上它就一直是非满二叉树。
还有，k==1时特判一下。
具体实现参看代码。

AC代码：

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

typedef long long LL;

LL n, k;

LL num[];

int main()

{

    int T;

    cin>>T;

    num[]=;

    while(T--)

    {

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

        if(k==){

            if(n==)

                printf("%d\n", );

            else if(n==)

                printf("%d\n",);

            else if(n==)

                printf("%d\n", );

            else

            {

                int k=n%;

                if(k==)

                    printf("%lld\n", n);

                else if(k==)

                    printf("%d\n", );

                else if(k==)

                    printf("%lld\n", n+);

                else

                    printf("%d\n", );

            }

            continue;

        }

        n--;

        int level=,t=;

        LL lm=, rm=;

        while(rm<n){

            t++;

            lm=rm+;

            rm=lm*k;

            num[t]=rm+;

        }

        LL res=,left,right,s=n+,m;

        t=;

        bool flag=;

            LL mid=n%k;//mid判断是否为满k叉树， m为非满k叉树的大小

            left=n-mid-lm+;

            //cout<<left<<endl;

            if(left&){

                res^=num[];

            }

            if(mid&)

                res^=num[];

            if(mid)

                flag=;

            m=(n-(n-)/k*k)*num[]+;

            //cout<<m<<endl;

            while(n)

            {

                //cout<<res<<'*'<<endl;

                t++;

                //cout<<t<<' '<<m<<endl;

                n=(n-)/k;

                if(n<=)

                    break;

                mid=n%k;

                lm=(lm-)/k;

                rm=(rm-)/k;

                //cout<<lm<<' '<<n<<' '<<rm<<endl;

                right=rm-n;

                left=n-lm+;

                if(flag||mid){

                    flag=;

                    left--;

                    res^=m;

                }

                if(left&)

                    res^=num[t];

                if(right&)

                    res^=num[t-];

                m+=(n-(n-)/k*k-)*num[t]+(((n-)/k+)*k-n)*num[t-]+;

            }

        res^=s;

        printf("%lld\n", res);

    }

    return ;

}