P1096题解

· · 题解

俺老孙又双叒叕来发题解了

其实这道题目故弄玄虚，步数其实就是普通汉诺塔的2倍。

然后我们看普通汉诺塔的步数：

方法（n个）：

先把上面n-1个移到第二个柱子，再把第n个移到第三个柱子，先把上面n-1个移到第三个柱子；

即

f(n)=2f(n-1)+1\\f(1)=1\\\rarr f(n)=2^n-1

那么题目要求输出的步数就是：

F(n)=2f(n)=2^{n+1}-2

上代码！

#include<bits/stdc++.h>
using namespace std;
int p,f[1005],l[1005],s[1005];
void s1()
{
    for(int i=1;i<=500;i++)
    {
        for(int j=1;j<=500;j++)
        {
            s[i+j-1]+=l[i]*f[j];
        }
    }
    for(int i=1;i<=500;i++)
    {
        s[i+1]+=s[i]/10;
        s[i]%=10;
    }
    memcpy(l,s,sizeof(l));
}
void s2(){
    memset(s,0,sizeof(s));
    for(int i=1;i<=500;i++)
    {
        for(int j=1;j<=500;j++)
        {
            s[i+j-1]+=f[i]*f[j];
        }
    }
    for(int i=1;i<=500;i++)
    {
        s[i+1]+=s[i]/10;
        s[i]%=10;
    }
    memcpy(f,s,sizeof(f));
}
int main(){
    cin>>p;
    p++;
    l[1]=1;
    f[1]=2;
    while(p!=0)
    {
        if(p%2==1)
        {
            memset(s,0,sizeof(s));
            s1();
        }
        p/=2;
        s2();
    }
    l[1]-=2;
    bool flag=0;
    for(int i=500;i>=1;i--) 
    {
        if(!l[i]&&!flag)continue;
        cout<<l[i];flag=1;
    }
    return 0;
}