Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

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$$lfloor$frac{i-1}{k}$rfloor$. 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)$, denoting the number of test cases. 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 [cpp] 2 5 2 5 3 [/cpp] #### Sample Output [cpp] 7 6 [/cpp] #### Source 2017 Multi-University Training Contest – Team 7 #### 题解： 赛后发现非常可写。只是我不知道从1开始异或的规律(逃)。 从一开始连续异或到 n 的连续XOR值 if n % 4==1 XOR= 1 if n % 4==2 XOR= n+1 if n % 4==3 XOR= 0 if n % 4==0 XOR= n #### Code [cpp] #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int t;scanf(“%d”,&t); while(t–) { ll n,k;scanf(“%lld%lld”,&n,&k); if(k==1) { ll kase = n%4; if(kase==1) printf(“1$n”);
else if(kase==2) printf(“%lld$n”,n+1); else if(kase==3) printf(“0$n”);
else printf(“%lld$n”,n); continue; } //n==27 k==3 ll ans = n; //i’s par = (i-1)/k while(1) { if(n-1<=k) { if((n-1)%2) ans ^= 1; break; } ll now = 1, x = 1;//x 全满k叉树当前层的节点总数, now 当前层的最左边节点序号 while(now + xk<=n-1) x *= k, now += x; ll last = n – now;//最后一层节点数 ll l = (last-1)/x;//唯一 一颗不满k叉树得左边合法树对应的父节点个数 ll r = k-l-1;//右边已合法树对应父亲节点的个数 if(l%2==1) ans ^= now;// if(r%2==1) ans ^= (now-x); n -= l now + r*(now-x)+1; ans ^= n; } printf(“%lld$n”,ans);
}
}

[/cpp]

This site uses Akismet to reduce spam. Learn how your comment data is processed.