题解 P6232 【[eJOI2019]挂架】
Zesty_Fox
2020-06-02 17:14:29
更好的阅读体验:[cnblogs](https://www.cnblogs.com/acceptedzhs/p/13032385.html)
这道题跟 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:
```cpp
#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;
}
```