﻿HDU 6121 Build a tree-Ocrosoft

# Build a tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 796    Accepted Submission(s): 292

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).

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



Solution
2017 Multi-University Training Contest – Team 7

#define C11
#include <set>
#include <map>
#include <stack>
#include <string>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#ifdef C11
#include <tuple>
#include <regex>
#include <random>
#include <complex>
#endif
using namespace std;
/** const var def */
const double eps = 1e-8;
const int maxn = 1e7 + 10;
const int MAXN = maxn * 4;
const int MOD = 1000000007;
const double PI = 4 * atan(1.0);
/** type def */
typedef long long LL;
typedef pair<int, int> Pii;
typedef pair<LL, LL> Pll;
typedef vector<int> Vi;
typedef pair<double, double> Vec2;
#ifdef C11
using Vec3 = tuple<double, double, double>;
using Tp3 = tuple<int, int, int>;
#endif
/** easy def */
#define ms(a) memset(a,0,sizeof(a))
#define msr(a) memset(a,-1,sizeof(a))
/* first, second, position */
#define _f first
#define _s second
#define _p(_tp,_pos) get<_pos>(_tp)
/* operator */
Pii operator +(const Pii &x, const Pii &y) { return Pii(x.first + y.first, x.second + y.second); }
Pii operator -(const Pii &x) { return Pii(-x.first, -x.second); }
Pii operator -(const Pii &x, const Pii &y) { return x + (-y); }
Pii operator +=(Pii &x, const Pii &y) { return x = x + y; }
Pii operator -=(Pii &x, const Pii &y) { return x = x - y; }
#pragma region input&output
{
char CH; bool F = false;
for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar());
for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar());
F && (num = -num);
return num;
}
{
T num;
}
#ifdef C11
template<class T, class... Args>inline int read(T &t, Args &...args)
{
return t;
}
#endif
template<class T> inline void print(T p, char ed = '\n')
{
int stk[70], tp = 0;
if (p < 0) { putchar('-'); p = -p; }
if (!p) { putchar('0'); if (ed != '\0')putchar(ed); return; }
while (p) stk[++tp] = p % 10, p /= 10;
while (tp) putchar(stk[tp--] + '0');
if (ed != '\0')putchar(ed);
}
#ifdef C11
template<class T, class... Args>inline void print(T t, Args ...args)
{
print(t, '\0');
if (sizeof...(args))putchar(' ');
else putchar('\n');
print(args...);
}
#endif
#pragma endregion

int main()
{
while (N--)
{
LL n, k;
if (k == 1) // k==1 时特判
{
print(vector<LL>{ n, 1, n + 1, 0 }[n % 4]);
continue;
}
vector<LL> nodeCnt(2, 1);
LL ans = n, cnt;
LL depth = 1, pos = (n - 1 - 1) / k;
for (LL t = 1; *(end(nodeCnt) - 1) < n; nodeCnt.push_back((t *= k) + *(end(nodeCnt) - 1)), depth++); // 到某层时的节点数量和
if (n - nodeCnt[--depth] & 1)ans ^= 1;
for (LL cur = 2; depth > 1; depth--, cur++, pos = (pos - 1) / k)
{
LL left = nodeCnt[depth - 1], right = nodeCnt[depth] - 1; // 当前(depth)层左侧节点标号，右侧节点标号(从0开始)
LL fullCur = nodeCnt[cur], fullCurU = nodeCnt[cur - 1]; // 当前层左侧节点子树是满k叉树时子树大小，右侧子树是满k叉树时子树大小
if (pos - left & 1)ans ^= fullCur; // 左侧满k叉树节点数量是奇数
if (right - pos & 1)ans ^= fullCurU; // 右侧满k叉树节点数量是奇数
for (cnt = pos; cnt <= (n - 2) / k; cnt = cnt*k + 1); // 非满k叉树的子树大小
ans ^= fullCurU + n - cnt;
}
print(ans);
}
return 0;
}