地址：http://acm.split.hdu.edu.cn/showproblem.php?pid=6121
题面:
Build a tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1240 Accepted Submission(s): 509
Problem 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), denoting the number of test cases.
For each test case:
A single line contains two positive integers n,k(1≤n,k≤1018).
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.
A single line contains a nonnegative integer, denoting the answer.
Sample Input
2
5 2
5 3
5 2
5 3
Sample Output
7
6
6
Source
思路：
画了几个图后，会发现除了n-1号节点所在的链上需要特殊计算，其他字数都是满k叉树
所以递归下去计算即可，但对于1叉树要特判
#include <bits/stdc++.h> using namespace std; #define MP make_pair
#define PB push_back
typedef long long LL;
typedef pair<int,int> PII;
const double eps=1e-;
const double pi=acos(-1.0);
const int K=1e6+;
const int mod=1e9+; LL pp[],sum[];
LL go(LL x,LL y)
{
if(x==) return ;
LL cnt=,ret=;
if(y%==) return x;
while()
{
if(cnt==x) return ret;
cnt=cnt*y+;
ret^=cnt;
}
}
LL dfs(LL n,LL k,int d)
{
if(n==) return ;
LL pos=n-,ret;
for(int i=;i<=d-;i++) pos=(pos-)/k;
ret=dfs(n--(pos-)*sum[d-]-(k-pos)*sum[d-],k,d-);
if((pos-)&) ret^=go(sum[d-],k);
if((k-pos)&) ret^=go(sum[d-],k);
return ret^n;
}
int main(void)
{
LL n,k;
int t;cin>>t;
sum[]=pp[]=;
while(t--)
{
cin>>n>>k;
if(k==)
{
LL ans;
if(n%==) ans=n;
else if(n%==) ans=;
else if(n%==) ans=n+;
else if(n%==) ans=;
printf("%lld\n",ans);
continue;
}
int d=;
for(int i=;sum[i-]<n;i++,d++)
pp[i]=pp[i-]*k,sum[i]=sum[i-]+pp[i];
cout<<dfs(n,k,d)<<endl;
}
return ;
}