题解 | #循环汉诺塔#

#include <iostream>
// 87350326 887197658 444
using namespace std;
typedef long long LL;
const int N = 1e7;
const long long p = 1000000007;
LL hnt1(int i);
LL hnt2(int i);
int dp1[N], dp2[N];
int main() {
    int n;
    cin >> n;
    //避免递归过深，逐步处理，记忆化处理结果
  	for(int i = 1; i < n; i += 1000)
    {
        hnt1(i), hnt2(i);
    }
    cout << hnt1(n) << ' ' << hnt2(n);
}
LL hnt1(int i) {
    if(i == 1) dp1[1] = 1;
    if(dp1[i]) return dp1[i]; 
    LL step2 = hnt2(i - 1) % p;
    dp1[i] = (1 + step2 * 2) % p;
    return dp1[i];
}
LL hnt2(int i) {
    if (i == 1) dp2[1] = 2;
    if(dp2[i]) return dp2[i];
    LL step2 = hnt2(i - 1) % p;
    LL step1 = hnt1(i - 1) % p;
    dp2[i] = (2 + step1 + step2 * 2) % p; 
    return dp2[i];
}
// 64 位输出请用 printf("%lld")