题解 P6232 【[eJOI2019]挂架】

Zesty_Fox

2020-06-02 17:14:29

Solution

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