Build a tree

Posted on | In , ,

题目链接

题意

给一个$k$叉树，已知总结点数，计算所有结点$size$大小的异或和。

思路

我们可以把一层中相同大小的结点一起计算。若是一棵满$k$叉树，我们可以得到它的层数其实是很少的。最后一层的每个结点只有三种情况：
要么是满$k$的，要么是空的，要么是不满的。
我们可以把层数向下扩展，模拟出后面的大小，然后每一层计算相同的个数，异或到答案里面去。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
#define inf 1ll << 50
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		ll n,k;
		scanf("%lld%lld",&n,&k);
		if(k==1){
			ll tmp=n+1;
			ll ans=0;
			ll pos=0;
			while(pos<63 && (1LL<<pos)<=tmp){
				ll cnt=tmp/(1LL<<(pos+1))*(1LL<<pos);
				ll num=tmp%(1LL<<(pos+1));
				if(num<=(1LL<<pos)) num=0;
				else num=num-(1LL<<pos);
				cnt+=num;
				if(cnt & 1) ans^=(1LL<<pos);
				pos++;
			}
			printf("%lld\n",ans);
			continue;
		}
		ll res=n,tmp=1;
		ll num=0;
		while(res>=tmp){
			res-=tmp;
			num++;
			if(tmp>res/k){
				break;
			}
			tmp*=k;
		}
		ll tmp1=0,tmp2=0,tmp3=0;
		if(res>0){
			tmp1=res/k;
			tmp2=res%k;
			tmp3=tmp-tmp1-1;
		}
		else{
			ll tmpx=tmp;
			ll ans=0;
			ll tmpk=1;
			for(int i=1;i<=num;i++){
				if(tmpx&1) ans^=tmpk;
				tmpk=tmpk*k+1;
				tmpx/=k;
			}
			printf("%lld\n",ans);
			continue;
		}
		ll ans=0;
		if(res&1) ans^=1;
		ll tmpt1=k+1,tmpt2=tmp2+1,tmpt3=1;
		for(int i=1;i<=num;i++){
			if(tmp1&1) ans^=tmpt1;
			if(tmp3&1) ans^=tmpt3;
			ans^=tmpt2;
			tmpt2+=tmpt1*(tmp1%k)+tmpt3*(tmp3%k)+1;
			tmpt1=tmpt1*k+1; tmpt3=tmpt3*k+1;
			tmp1/=k; tmp3/=k;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

对于$k=1$情况的特判貌似还是个结论。

1
2
3
4
5
6
7
8
if(k==1){
			ll x=n%4;
			if(x==0) printf("%lld\n",n);
			else if(x==1) printf("1\n");
			else if(x==2) printf("%lld\n",n+1);
			else printf("0\n");
			continue;
		}

0%