# XDU1200题解（西电17年校赛E题）

2019-04-13 14:02发布

站内文章 / 模拟电子
17217 0 1412

XDU1200题解

题意

汉诺塔问题
本题将古老问题做了点改动，每一个圆盘有相同的两个，但是实际上这两个圆盘必须同时移动，所以只需要将最终步骤乘2即可。

笺释

自己推导了一下这个问题。
首先可知，要想把处于最下层的盘X移动到C柱，必须把其上的盘集合Q移动到B柱。
这是第一层划分:将X之上的盘集合Q移动到B柱，然后将盘X移动到C柱，然后将Q从B柱移动到C柱。
又可知，将Q移动到B柱和将Q移动到C柱实际上所需最小步骤是相同的，记作fq
至于为什么步骤相同,可由这样的对称关系解释:在将A上的盘集合Q移动到B或C的过程开始之前，B或C是完全对称的，或者说是无法区分的。
这样可得到答案fq+1+fq，也就得到了递推关系式，最后快速幂取模乘2即可。

完整代码

#include using namespace std; typedef long long LL; int p=2097151; long long n; LL quick_mod(LL a, LL b) { LL ans = 1; a %= p; while(b) { if(b & 1) { ans = ans * a % p; b--; } b >>= 1; a = a * a % p; } return ans; } int main() { while(~scanf("%lld",&n)) { LL ans=quick_mod(2,n)-1; ans*=2; ans%=p; printf("%lld ",ans); } }

热门文章