题意：询问n个点的完全k叉树，所有子树节点个数的异或总和为多少。
题解：对于树的每一层，我们可以分为三种节点：①满节点的k叉树②不满的k叉树③比第一种情况少一层的满节点的k叉树，然后从叶子节点开始不断转移到上一层。
AC代码：
[cpp] view plain copy print ? #include<vector> #include<list> #include<map> #include<set> #include<deque> #include<queue> #include<stack> #include<bitset> #include<algorithm> #include<functional> #include<numeric> #include<utility> #include<complex> #include<sstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<ctime> #include<cassert> #include<string> using namespace std; typedef long long ll; int main(void){ ll t; scanf("%lld",&t); while(t--){ ll n,k; scanf("%lld%lld",&n,&k); if(k==1) { ll t=n&3; if(t&1)printf("%lld\n",t/2u^1); else printf("%lld\n",t/2u^n); continue; } ll sum=1; ll a=0,b=0,c=0; ll s=k; ll flag=0; while(sum<=n-s) { sum=sum+s; if((double)s>1e18/(double)k) { flag=1; break; } s=s*k; } ll sheng=n-sum; if(flag==0)s/=k; a=sheng/k; b=sheng%k==0?0:1; c=s-a-b; ll ans=sheng%2; ll vala=k+1; ll valb; if(sheng%k!=0)valb=sheng%k+1; else valb=0; ll valc=1; while(a+b+c>1) { if(a%2==1) ans=ans^vala; if(b%2==1) ans=ans^valb; if(c%2==1) ans=ans^valc; if(a%k!=0) { valb=valb+vala*(a%k)+(k-b-a%k)*valc+1; b=1; } else valb=valb+(k-1)*valc+1; a=a/k; vala=vala*k+1; if(c%k!=0)b=1; c=(c-c%k)/k; valc=valc*k+1; } printf("%lld\n",ans^n); } return 0; } /*1 3 3 6 7 6 7 13 13 15 15 13 13 15 15 26 27 26 27 30 */ #include<vector> #include<list> #include<map> #include<set> #include<deque> #include<queue> #include<stack> #include<bitset> #include<algorithm> #include<functional> #include<numeric> #include<utility> #include<complex> #include<sstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<ctime> #include<cassert> #include<string> using namespace std; typedef long long ll; int main(void){ ll t; scanf("%lld",&t); while(t--){ ll n,k; scanf("%lld%lld",&n,&k); if(k==1) { ll t=n&3; if(t&1)printf("%lld\n",t/2u^1); else printf("%lld\n",t/2u^n); continue; } ll sum=1; ll a=0,b=0,c=0; ll s=k; ll flag=0; while(sum<=n-s) { sum=sum+s; if((double)s>1e18/(double)k) { flag=1; break; } s=s*k; } ll sheng=n-sum; if(flag==0)s/=k; a=sheng/k; b=sheng%k==0?0:1; c=s-a-b; ll ans=sheng%2; ll vala=k+1; ll valb; if(sheng%k!=0)valb=sheng%k+1; else valb=0; ll valc=1; while(a+b+c>1) { if(a%2==1) ans=ans^vala; if(b%2==1) ans=ans^valb; if(c%2==1) ans=ans^valc; if(a%k!=0) { valb=valb+vala*(a%k)+(k-b-a%k)*valc+1; b=1; } else valb=valb+(k-1)*valc+1; a=a/k; vala=vala*k+1; if(c%k!=0)b=1; c=(c-c%k)/k; valc=valc*k+1; } printf("%lld\n",ans^n); } return 0; } /*1 3 3 6 7 6 7 13 13 15 15 13 13 15 15 26 27 26 27 30 */