[LOJ3196] 挂架

Description

给定深度为 (n le 10^{18}) 的满二叉树，层次标记为 (0 sim n-1)，要依次染色 (k) 个叶子，且每次染色后任意分支点的左右子树中被染色结点数量的差不能超过 (1)（左边减右边），求第 (k) 个被染色的叶子的编号。

Solution

显然递归处理，设递归函数 (dfs(l,k)) 表示当前层次为 (l)，排名为 (k)，则

• 若 (2|p)，则最晚更新点在 (p) 的右子树，于是 (dfs(l,k)=dfs(l+1,k/2)+2^{n-l-1})。
• 否则，最晚更新点在 (p) 的左子树，于是 (dfs(l,k)=dfs(l+1,k/2+1))。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;
const int mod = 1e+9+7;
const int dbg = 0;

int n,k,pw[N];

int dfs(int l,int k)
{
    if(l==n-1) return k;
    if(k&1) return (dfs(l+1,k/2+1))%mod;
    else return (dfs(l+1,k/2)+pw[n-l-1])%mod;
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n>>k;
    pw[0]=1;
    pw[1]=2;
    for(int i=2;i<=n;i++) pw[i]=pw[i-1]*2%mod;
    cout<<dfs(0,k)<<endl;

    if(dbg) system("pause");
}