题解 | #循环汉诺塔#

#include <iostream>
#include<vector>
using namespace std;
using i64 =long long;
const int mod = 1e9+7;
//画几个图可以推出来这些关系
//注意是循环的
//比如 在有三个盘子的情况下，将c上的两个盘子移动到a
//就相当于上一次的两个盘子移动到b的情况
int main() {
    int n;
    cin>>n;
    i64 tob=0,toc=0;

    for(int i=1;i<=n;i++)
    {
        i64 lastb=tob;
        i64 lastc=toc;
        //n-1个盘子到c，第n个到b,然后n-1个盘子到c
        tob = (lastc + 1 + lastc)%mod;
        //n-1个盘子到c，第n个到b,然后n-1个盘子到a,第n个到c,n-1个到c
        toc = (lastc + 1 + lastb + 1 + lastc)%mod;
        // cout<<tob<<' '<<toc<<'\n';
    }
    cout<<tob<<' '<<toc;
    

}
// 64 位输出请用 printf("%lld")