hdu 6121 Build a tree

/**

 * 题意：一棵 n 个点的完全 k 叉树，结点标号从 0 到 n - 1，求以每一棵子树的大小的异或和。

 * 解法：k叉树，当k=1时，特判，用xorn函数，具体解释：http://blog.csdn.net/a3630623/article/details/12371727

 * k不等一1；我们dfs求解，当是满k叉树，可以很快求的；每层最对可能三类树，少一层的满k叉树，

 * 少两层的满k叉树，不满的子树dfs求解。

 */

#include <cstdio>

#include <cstring>

#include <cctype>

#include <cmath>

#include <set>

#include <map>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <time.h>

using namespace std;

typedef long long LL;

const int INF=2e9+1e8;

const int MOD=1e9+7;

const double eps=0.0000000001;

void fre()

{

    freopen("test.in","r",stdin);

    freopen("test.out","w",stdout);

}

#define MSET(a,b) memset(a,b,sizeof(a))

const int maxn=1e6+10;

LL ans;

LL xorn(LL n) //1～n连续异或的值；

{

    LL t = n & 3ll;

    if (t & 1ll)

        return t / 2ll ^ 1ll;

    return t / 2ll ^ n;

}

LL xorpow(LL a,LL b) // b个a连续异或

{

    if(b%2==0) return 0;

    else return a;

}

LL getnn(LL n,LL k) //n层k叉树的加点个数

{

    LL res=0,t=1;

    while(n--)

    {

        res+=t;

        t*=k;

    }

    return res;

}

LL man(LL n,LL k) //n层满k叉树的异或值；

{

    if(n<=0) return 0;

    LL res=0,sz=getnn(n,k),t=1;

    for(LL i=1;i<=n;i++)

    {

        res^=xorpow(sz,t);

        sz=(sz-1)/k;

        t*=k;

    }

    return res;

}

void dfs(LL n, LL k)

{

    if(n==0) return ;

    LL deep = 0;

    for (LL m = n,t=1;m>0; t*=k) //得到深度

    {

        m-=t;

        deep++;

    }

    if(getnn(deep,k)==n) //判断是否是满k叉树？如果是直接得出答案；

    {

        ans^=man(deep,k);

        return ;

    }

    else

    {

        if(deep<=2) //深度为2，不用在递归了，到头了，直接求异或

        {

            ans^=n;

            ans^=xorpow(1ll,n-1);

            return ;

        }

        else

        {

            ans ^= n;

            LL tp=n-getnn(deep-1,k);

            for(LL i=1;i<=deep-2;i++) tp/=k;

            ans^=(xorpow(man(deep-1,k),tp));//深度-1的满k叉树

            ans^=(xorpow(man(deep-2,k),k-tp-1));//深度-2 的满k叉树

            dfs(n-1-tp*getnn(deep-1,k)-getnn(deep-2,k)*(k-1-tp),k); //剩下的子树，dfs求；

        }

    }

}

int main()

{

    int ncase;

    scanf("%d",&ncase);

    while(ncase--)

    {

        LL n,k;

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

        if(k==1)

        {

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

        }

        else

        {

            ans=0;

            dfs(n,k);

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

        }

    }

    return 0;

}

/**************************************************/

/**             Copyright Notice                 **/

/**  writer: wurong                              **/

/**  school: nyist                               **/

/**  blog  : http://www.cnblogs.com/coded-ream/  **/

/**************************************************/

/**

1000000000000000000 1000000000000000000

 */
巴特西

hdu 6121 Build a tree

最新文章

热门文章
