自动搬运

查看原文

来自洛谷，原作者为

	Zesty_Fox Life, the Universe, and Everything.

搬运于2025-08-24 22:18:48，当前版本为作者最后更新于2020-06-02 17:14:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读体验：cnblogs

这道题跟 CSP-S 2019 D1T1 有点像。

我们先来模拟一下 $n=4$ 的情况。

不难得出，最后的衣架挂钩顺序：

下标：  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
顺序：  1  9  5 13  3 11  7 15  2 10  6 14  4 12  8 16

可以发现，得到的顺序构成的序列中左半部分全是奇数，右半部分全是偶数。我们把它分开：

1 9 5 13 3 11 7 15
2 10 6 14 4 12 8 16

奇数部分每个数 $+1$ 再 $\div 2$，偶数部分每个数 $\div 2$，可以得到：

1 5 3 7 2 6 4 8
1 5 3 7 2 6 4 8

可以发现，上下部分变得一样了！不仅如此，这还恰巧是 $n=3$ 的情况！

所以，我们自然而然想到递归。

如果深度已经是 $n-1$ 了，直接将答案加上当前序号（第一层深度为 $0$）；

如果当前序号为奇数，即在左半部分，则把它 $+1$ 再 $\div 2$，继续递归；

如果当前序号为偶数，即在右半部分，则把它 $\div 2$，同时答案加上 $2^{n-\mathit{depth}-1}$（左半部分的长度），继续递归。

Code:

#include <bits/stdc++.h>
#define int long long
int n,k,MOD=1e9+7;
int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1) res=(res*x)%MOD;
        x=(x*x)%MOD;y>>=1;
    }
    return res;
}
int dfs(int x,int dep) {
    return dep==n?x:(x%2?dfs((x+1)/2,dep+1):(dfs(x/2,dep+1)+qpow(2,n-dep))%MOD);
}
signed main(){
    std::cin>>n>>k;std::cout<<dfs(k,1)%MOD<<std::endl;
    return 0;
}