[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’还有输入

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

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

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

ac代码

#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;
}