hdu6121 build a tree（树）

题解：

可以考虑每一层结点的子树大小

必定满足下面的情况，即

a,a,a,a,a,a,b,c,c,c,c........

然后每一层依次往上更新，结果是不变的

一共有logn层，所以依次扫上去，统计结果即可

注意到k=1的时候，是一条链，需要特殊处理orz

这个打表可以发现明显的规律，也是二进制的一种容斥吧

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long LL;

typedef long long ll;

LL n, k;

LL mypow(LL a, LL b){

    if( pow((double)a, b) > 1.5e18) return 1e18;

    LL ans = ; for(; b; b >>= ) { if(b&) ans *= a; a *= a; } return ans;

}

int main()

{

    int T;

    cin>>T;

    while(T--){

        cin>>n>>k;

        if(n == ){

            cout<<<<endl;

            continue;

        }

        if(k == ){

            LL t = n%;

            if(t == ) cout<<<<endl;

            else if(t == ) cout<<n+<<endl;

            else if(t == ) cout<<<<endl;

            else cout<<n<<endl;

            continue;

        }

        LL d = , sum = ;

        while(sum + mypow(k, d) <= n) sum += mypow(k, d), d++;

        if(sum == n){

            d--;

            LL ans = , sz = ;

            while(d != -){

                LL N = mypow(k, d);

                if(N&) ans ^= sz;

                sz = +sz*k;

                d--;

            }

            cout<<ans<<endl;

            continue;

        }

        LL N = n - sum, ans = ;

        LL X = N, L = , R = , Xv = , D = d;

        while(d){

            LL dL = mypow(k, d);

            ans ^= Xv;

            if((X-)&) ans ^= L;

            if((dL-X)&) ans ^= R;

            LL Nl = X-;

            LL Nx = Nl/k*k + , Nfx = X-Nx;

            LL Ny = Nx+k-, Nfy = Ny-X;

            Xv = Nfx*L + Nfy*R + Xv + ;

            if((double)L*k < 1.5e18) L = +L*k;

            R = +R*k;

            X = (Nx-)/k + ;

            d--;

        }

        ans ^= Xv;

        cout<<ans<<endl;

    }

}