题解 P6232 【[eJOI2019]挂架】

· · 题解

更好的阅读体验：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;
}