[uva10479]The Hendrie Sqquence

The Hendrie Sequence

题意

给定一段序列的生成方式,问第$n$个元素是多少。 $0<n<2^{63}$。

  • $H(1) = 0$
  • $H(n) = H(n-1)$中的每个元素$a_i$,那么每个元素就生成一个小子序列$0,0,0,0,0,a_i+1$其中$0$的个数是$a_i$。
  • 除了第一个元素之外的所有元素都要进行这种变化

举个例子,

$H(1) = 0$

$H(2) =0,1$ //$0$变成了$0,1$

$H(4) = 0,1,0,2$ //$0$ 变成了$0,1$, $1$变成了$0,2$

$H(8) = 0,1,0,2,1,0,0,3$ //$0$ 变成了$0,1$, $1$变成了$0,2$ ,$2$变成了$0,0,3$

题解

找规律,我们可以发现每次都变化之后序列的长度都翻了一倍。所以我们单独把他增长的序列拿出来看。可以用心去发现这样一个规律。

  • 定义增长的序列为$b_i$
  • $b_i$是由$1$个$b_{i-1}$,$2$个$b_{i-2}$,$3$个$b_{i-3}$,$4$个$b_{i-4}$…$i$个$b_{0}$ ,再加上一个单独的数字$i$。以此类推出来的。

那么我们就可以从第$n$个元素表示在它属于的那次增长中,它排第几个递归到最初的那几个元素中去,要判断一下范围。

由于题目中的数据比较极限,所以能用unsigned long long 还是用unsigned long long 吧。

如果用unsigned long long。一般数据量输入很小 可以用cin很靠谱。但是要把endl换成’\n’还有输入

1
2
std::ios::sync_with_stdio(false);
cin.tie(0);

或者判断他是$2$的几次幂的时候可以这样子判断最高位的$1$在哪里。

1
2
3
4
ll n; int dep=0;
ll temp = n;
while(temp) temp>>=1,dep++;
dep--;

ac代码

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
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
ll n;
ll lie[10][20] ={ {0}, {1}, {0,2}, {1,0,0,3},{0,2,1,1,0,0,0,4}};
ll solve(ll x,int dep){
if(dep<5){
return lie[dep][x];
}
ll st = 0;
rep(i,2,dep+1){
ll temp = pow(2,dep-i-1);
if(i==dep) temp = 1;
if(x<temp*(1ll*i-1ll)+st) return solve((x-st)%temp,dep-i);
st += temp*(ll)(i-1);
}
return dep;
}
int main(){
#ifdef LOCAL
freopen("4.in","r",stdin);
#endif
std::ios::sync_with_stdio(false);
cin.tie(0);
while(cin>>n && n){
int dep = 0;ll temp = 1;
n--;
ll tn = n;
while(tn) tn/=2,dep++;
temp<<=(dep-1);
n = n - temp;
cout<<solve(n,dep);
cout<<'\n';
}

return 0;
}