【链接】点击打开链接
【题意】
【题解】
考虑如下的一棵k=3叉树,假设这棵树恰好有n个节点.
因为满的k叉树,第i层的节点个数为k^(i-1);
则我们找到最大的d;
使得
k^0+k^1+..+k^(d-1) <=n
自此,我们会发现,整棵树可以分成若干个树的深度大小为d和d-1的满k叉树。
如上图,d=3,两个圈起来的,就是一个深度为3的满k叉树和一个深度为2的满k叉树。
当然,还可能会有一个子树,它不是满的k叉树。
如上图中没有被圈出来的部分.
深度大小为d的满k叉树的个数,可以用rest =
n-(k^0+k^1+..+k^(d-1))算出来;
它的个数就是rest/num[d],(其中num[d]表示第d层的满k叉树的节点个数.)
就是每num[d]个最下边的那些点可以将一个深度为d-1的满k叉树组成深度为d的满k叉树。
然后看看rest%num[d]是不是为0.
如果不为0的话,就会有一棵子树不是满k叉树;
则肯定还有k-rest/num[d]-1棵是深度为d-1的满k叉树。
然后思考那个不是满k叉树的。
会发现.那棵子树的问题。仍然是我们最开始面临的问题。
是可以递归解决的!
获取那个子树的大小,然后递归解决就好!
(深度为d和深度为d-1的满k叉树的子树异或和,单独写一个dfs来做就好)
(不要忘记有多个子树,所以对应的答案要异或和子树的个数对应次数)
k=1的情况要单独处理。找规律就好。就是1^2^3..^n的值。。
(要注意根节点的儿子不够k个的情况。。那个时候就不用递归了,直接处理答案)
【错的次数】
0
【反思】
编程比较难。思路不难想。
【代码】
#include <bits/stdc++.h>
using namespace std;
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define oi(x) printf("%d",x)
#define ol(x) printf("%lld",x)
#define os(x) printf(x)
#define LL long long
LL k,num[100],tot[100],ans;
LL f(LL x,LL y){
if (y&1)
return x;
else
return 0;
}
LL dfs(int d){
LL now = 0,temp = 0;
rep2(i,d,1){
temp = temp*k + 1;
now ^= f(temp,num[i]);
}
return now;
}
void solve(LL n){
num[1] = 1,tot[1] = 1;
int d = 1;
while (1){
d++;
num[d] = num[d-1]*k;
tot[d] = tot[d-1]+num[d];
if (tot[d]>n) break;
}
d--;
LL numdp1 = 0,numd = 0,rest = n-tot[d];
if (d == 1 && rest <= k){
ans ^= f(1,rest);
ans ^= n;
return;
}
numdp1 = rest/num[d],numd = k - numdp1 - 1;
LL trest = rest%num[d];
ans ^= f(dfs(d),numdp1);
LL temp1 = dfs(d-1);
ans ^= f(temp1,numd);
if (trest==0)
ans ^= temp1;
else
solve(trest+tot[d-1]);
ans ^= n;
}
int main(){
//freopen("D:\rush.txt","r",stdin);
int T;
ri(T);
while (T--){
LL n;
rl(n),rl(k);
ans = 0;
if (k==1){
n--;
if (n%4==0) ans = 1;
if (n%4==1) ans = n + 2;
if (n%4==2) ans = 0;
if (n%4==3) ans = n+1;
}else
solve(n);
ol(ans);puts("");
}
return 0;
}