题意：有一棵n个点的有根树，标号为0到n−1，i号点的父亲是(i-1)/k号点，求所有子树大小的异或和 1<=n,k<=1e18
思路：这是一棵完全k叉树，考虑根的所有孩子，最多只有一个不是满k叉树，对这个孩子进行递归处理即可。k>1时只有log层，直接做就到底就好了，k=1时要特判。
AC代码：
#include "iostream" #include "iomanip" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define step(x) fixed<< setprecision(x)<< #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ll long long #define endl (" ") #define ft first #define sd second #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const ll mod=1e9+7; const ll INF = 1e18+1LL; const int inf = 1e9+1e8; const double PI=acos(-1.0); const int N=1e5+100; ll c[105],sum[105],n,k,ans; ll dep(ll x, ll k, ll d){ //求深度 if(x==0) return d; else return dep((x-1)/k, k, d+1); } ll fun(ll x, ll k){ //节点数为x的满k叉树的答案 if(x==0) return 0; ll d=dep(x-1, k,1); ll ret=0, t=1; for(ll i=d; i>=1; --i){ if(c[i]&1) ret^=t; t=t*k+1; } return ret; } ll fat(ll m, ll k){ //找祖先 if(m<=k){ return m; } return fat((m-1)/k, k); } void dfs(ll x, ll k){ //bug(x) char c=getchar(); if(x==1){ ans^=1; return; } ll d=dep(x-1,k,1); if(x==sum[d]){ ans^=fun(sum[d], k); return; } ans^=x; ll u=fat(x-1,k); if((u-1)&1) ans^=fun(sum[d-1], k); if((k-u)&1) ans^=fun(sum[d-2], k); x-=(u-1)*sum[d-1]+(k-u)*sum[d-2]+1; //cout<< "x=" <<x<<endl; dfs(x,k); } int main(){ ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int T; cin>>T; while(T--){ cin>>n>>k; mem(sum,0); for(ll i=1,t=1; t<=INF,i<=60; ++i,t*=k){ c[i]=t,sum[i]+=sum[i-1]+c[i]; } if(k==1){ ll t=(n+3)/4, x=n%4; if(x==1) ans=1; if(x==3) ans=0; if(x==2) ans=4*t-1; if(x==0) ans=4*t; cout<<ans<<endl; continue; } ans=0; dfs(n,k); cout<<ans<<endl; } return 0; }