HDU 6121 Build a tree （技巧）

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)

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

思路

考慮任意一個高度為 h 的完全 k

對于根節點的 k 個孩子構成的 k

• cnt[i] ，第 i
• sum[i] ，高為 i 的滿 k 叉樹節點個數

• xor[i] ，高為 i 的滿 k

• 我們知道， x⊕x=0 ，一個數自身的偶數次異或值為 0

  是以我們設 F(x,y) 為将 x 連續異或 y 次，顯然其結果與 y

  在滿 k 叉樹階段， xor[dep]=sum[dep]⊕F(xor[dep−1],k) ，而在其他階段，我們隻需要遞歸将這顆樹分解為若幹個滿 k<script type="math/tex" id="MathJax-Element-34">k</script> 叉子樹同樣處理即可。

AC 代碼

#include<bits/stdc++.h>
typedef __int64 LL;
using namespace std;
const int maxn =105;
LL cnt[maxn];       // 第 i 層的節點個數
LL sum[maxn];       // 高為 i 的滿 k 叉樹節點個數
LL xxor[maxn];      // 高為 i 的滿 k 叉樹所有子樹異或和
LL n,k;

inline LL F(LL a,LL b)
{
    return b&1?a:0;
}

LL dfs(LL dep,LL add)
{
    if(dep==0)return 0;
    return (sum[dep] + add)^F(sum[dep],add/cnt[dep])^F(sum[dep-1],k-1-add/cnt[dep])^dfs(dep-1,add%cnt[dep]);
}

LL solve()
{
    if(k==1)        // 對 1 特判
    {
        int mo = n%4;
        if(mo==0)
            return n;
        else if(mo==1)
            return 1;
        else if(mo==2)
            return n+1;
        else
            return 0;
    }
    int dep=1;
    sum[dep]=cnt[dep]=xxor[dep]=1;
    while((n-sum[dep])/k>=cnt[dep])     // 枚舉深度（所有滿節點的層）
    {
        dep++;
        cnt[dep] = cnt[dep-1]*k;
        sum[dep] = sum[dep-1] + cnt[dep];
        xxor[dep] = sum[dep]^F(xxor[dep-1],k);
    }
    return dfs(dep,n-sum[dep]);
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        LL ans;
        cin>>n>>k;
        ans=solve();
        cout<<ans<<endl;
    }
    return 0;
}