第三届中国计量大学ACM程序设计竞赛个人赛（同步赛）——N题

链接：https://ac.nowcoder.com/acm/contest/5795/N

这题是整场比赛过的人最多的题。

这题是汉诺塔的变种题，那既然是汉诺塔的变种我们肯定不可以忘记最原始的汉诺塔题是怎么做的啦。我们来复习一下：
求普通汉诺塔移动n个盘子的最小移动次数。

设 为移动n个盘子由出发柱经过辅助柱移动到目标柱的最小移动次数，边界： ，这是因为我们可以直接把一个盘子移动到目标柱。

当 时， ,这是因为我们先把 个盘子移动到辅助柱，把第n个盘子移动到目标柱，最后把剩下的个盘子移动到目标柱。好的原始汉诺塔就是这样，我们来看这题。

这题要求是无论从A到C还是从C到A都必须经过B柱，那我们应该怎么做呢？ 那我们也仿照普通汉诺塔的思路，设 为n个盘子由A到C或者由C到A的次数，B我们只是用来过渡的，除了第n个其他都不会停留在B，否则就会卡住了。仿照普通汉诺塔的过程，那么递推公式就是： ,我们可以通过3次n-1个盘子由A到C和由C到A的操作，和第n个盘子由A到B和由B到C的操作完成。

代码为：（注意是多组数据，必须预处理再输出每一组询问）

#include<iostream>
using namespace std;
long long t,n,f[1000006];
const long long mod=1e9+7;
int main()
{
    ios::sync_with_stdio(false);
    f[1]=2;
    for(int i=2;i<=1000002;i++)
    {
        f[i]=((3*f[i-1])%mod+2)%mod;
    }
    cin>>t;
    while(t--)
    {
        cin>>n;
        cout<<f[n]<<endl;
    }
}

可是我们并不满足，要是n为 ，这个算法也过不了，我们继续做下去。

大家都还记得普通汉诺塔的通项公式是 ,这题我们也可以推出通项公式

由上面的公式变形为：

这个就是高中数列基本题了，我们可以得到 是一个首项为3，公比为3的等差数列，所以
代码：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
int t,n;
const int mod=1e9+7;
int kuai(int a,int b,int c)
{
    long long ans=1;
    a%=c;
    while(b>0)
    {
        if(b%2)
        {
            ans=ans*a%c;
        }
        b/=2;
        a=a*a%c;
    }
    return ans;
}
signed main()
{
    cin>>t;
    while(t--)
    {
        scanf("%lld",&n);
        printf("%lld\n",kuai(3,n,mod)-(int)1);
    }
}