Build a tree

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

Problem Description

HazelFan wants to build a rooted tree. The tree has

Input

The first line contains a positive integer

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

Source

2017 Multi-University Training Contest - Team 7

思路：

　　画了几个图后，会发现除了n-1号节点所在的链上需要特殊计算，其他字数都是满k叉树

　　所以递归下去计算即可，但对于1叉树要特判

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define MP make_pair
 6 #define PB push_back
 7 typedef long long LL;
 8 typedef pair<int,int> PII;
 9 const double eps=1e-8;
10 const double pi=acos(-1.0);
11 const int K=1e6+7;
12 const int mod=1e9+7;
13 
14 LL pp[100],sum[100];
15 LL go(LL x,LL y)
16 {
17     if(x==0) return 0;
18     LL cnt=1,ret=1;
19     if(y%2==0) return x;
20     while(1)
21     {
22         if(cnt==x) return ret;
23         cnt=cnt*y+1;
24         ret^=cnt;
25     }
26 }
27 LL dfs(LL n,LL k,int d)
28 {
29     if(n==1) return 1;
30     LL pos=n-1,ret;
31     for(int i=1;i<=d-2;i++) pos=(pos-1)/k;
32     ret=dfs(n-1-(pos-1)*sum[d-1]-(k-pos)*sum[d-2],k,d-1);
33     if((pos-1)&1) ret^=go(sum[d-1],k);
34     if((k-pos)&1) ret^=go(sum[d-2],k);
35     return ret^n;
36 }
37 int main(void)
38 {
39     LL n,k;
40     int t;cin>>t;
41     sum[1]=pp[1]=1;
42     while(t--)
43     {
44         cin>>n>>k;
45         if(k==1)
46         {
47             LL ans;
48             if(n%4==0) ans=n;
49             else if(n%4==1) ans=1;
50             else if(n%4==2) ans=n+1;
51             else if(n%4==3) ans=0;
52             printf("%lld
",ans);
53             continue;
54         }
55         int d=1;
56         for(int i=2;sum[i-1]<n;i++,d++)
57             pp[i]=pp[i-1]*k,sum[i]=sum[i-1]+pp[i];
58         cout<<dfs(n,k,d)<<endl;
59     }
60     return 0;
61 }