递推做法

1. 分析问题：

   • 当 Alice 一次能拿两个圆盘时，我们可以将问题划分为更小的子问题。具体来说，我们将 \(n\) 层塔分为两部分：上面 \(n-2\) 层和最下面的两个圆盘。
   • 首先将 \(n-2\) 层从起始柱移动到辅助柱，这需要 \(f_{n-2}\) 次操作。
   • 然后将剩余的两个圆盘一起从起始柱移动到目标柱，这只需要 \(2\) 次操作。
   • 最后将 \(n-2\) 层从辅助柱移动到目标柱，需要再次进行 \(f_{n-2}\) 次操作。

2. 推导递推关系：
   \[
   f_i = 2 * f_{i-2} + 2
   \]

   • 其中 \(f_{i-2}\) 是移动 \(n-2\) 层所需的次数，而 \(2\) 是移动最下面两个圆盘的操作次数。

矩阵加速递推

直接递推肯定无法通过，我们可以用矩阵进行加速。

首先观察上面的递推式，有 \(f[i], f[i-2], 1\) 这三项，那我们可以设计一个四行的列向量：

\[
\vec{v} = \begin{pmatrix}
f[i-1] \\
f[i-2] \\
f[i-3] \\
1
\end{pmatrix}
\]

考虑对其进行变换。

从矩阵乘法的定义入手

\(A \times B\) 即为 \(A\) 的行向量逐个点乘 \(B\) 的列向量

很容易得出这样的一个四维方阵：

\[
A = \begin{bmatrix}
0 & 2 & 0 & 2 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}
\]

让我们看一下这样会出现什么结果

\[
\begin{bmatrix}
0 & 2 & 0 & 2 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}
\begin{pmatrix}
f[i-1] \\
f[i-2] \\
f[i-3] \\
1
\end{pmatrix}
\text{=}
\begin{pmatrix}
2*f[i-2] + 2 \\
f[i-1] \\
f[i-2] \\
1
\end{pmatrix}
\text{=}
\begin{pmatrix}
f[i] \\
f[i-1] \\
f[i-2] \\
1
\end{pmatrix}
\]

初始时，有

\[
\vec{v} = \begin{pmatrix}
4 \\
2 \\
1 \\
1 \\
\end{pmatrix}
\]

则

\[
B = A \vec{v} = \begin{pmatrix}
8 \\
4 \\
2 \\
1
\end{pmatrix}
\]

此时 \(B\) 的第一行第一列的数就是 \(f[4]\) 的值。
以此类推，对 \(\vec{v}\) 左乘 \(n\) 次 \(A\)，结果矩阵的第一行第一列的数就是 \(f[3+n]\) 的值。

AC Code

#include<bits/stdc++.h>
#define LL long long
#define sz 4
#define MOD 998244353
using namespace std;

struct mat {
    LL a[sz][sz];
    
    mat() { memset(a, 0, sizeof a); }
    
    mat operator-(const mat& T) const {
        mat res;
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j) {
                res.a[i][j] = (a[i][j] - T.a[i][j]) % MOD;
            }
        return res;
    }
    
    mat operator+(const mat& T) const {
        mat res;
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j) {
                res.a[i][j] = (a[i][j] + T.a[i][j]) % MOD;
            }
        return res;
    }
    
    mat operator*(const mat& T) const {
        mat res;
        int r;
        for (int i = 0; i < sz; ++i)
            for (int k = 0; k < sz; ++k) {
                r = a[i][k];
                for (int j = 0; j < sz; ++j)
                    res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
            }
        return res;
    }
    
    mat operator^(LL x) const {
        mat res, bas;
        for (int i = 0; i < sz; ++i) res.a[i][i] = 1;
        for (int i = 0; i < sz; ++i)
            for (int j = 0; j < sz; ++j) bas.a[i][j] = a[i][j] % MOD;
        while (x) {
            if (x & 1) res = res * bas;
            bas = bas * bas;
            x >>= 1;
        }
        return res;
    }
};

void dump(mat m){
    for(int i=0; i<sz; i++){
        for(int l=0; l<sz; l++){
            cerr<<m.a[i][l]<<" ";
        }
        cerr<<endl;
    }
}

int main(){
    int n;
    cin>>n;

    mat mata;
    mata.a[0][0] = 0;
    mata.a[0][1] = 2;
    mata.a[0][2] = 0;
    mata.a[0][3] = 2;
    mata.a[1][0] = 1;
    mata.a[1][1] = 0;
    mata.a[1][2] = 0;
    mata.a[1][3] = 0;
    mata.a[2][0] = 0;
    mata.a[2][1] = 1;
    mata.a[2][2] = 0;
    mata.a[2][3] = 0;
    mata.a[3][0] = 0;
    mata.a[3][1] = 0;
    mata.a[3][2] = 0;
    mata.a[3][3] = 1;

    mat matb;
    matb.a[0][0] = 4;
    matb.a[1][0] = 2;
    matb.a[2][0] = 1;
    matb.a[3][0] = 1;
    
    switch (n) {
    case 1:
        cout<<1<<endl;
        return 0;
    case 2:
        cout<<2<<endl;
        return 0;
    case 3:
        cout<<4<<endl;
        return 0;
    }
    
    mata = mata^(n-3);
//  dump(matb);
    mat ans = mata * matb;
//  dump(ans);
    
    cout<<ans.a[0][0]<<endl;
    
    return 0;
}

本题考查：数学，动态规划（部分分），找规律。

\(20\) 分做法：手玩 \(n=1,2,3\) 的情况即可，答案分别为 \(1,2,4\) 。

\(40\) 分做法：暴力搜索，找到最少的操作次数。

\(60\) 分做法：发现递推关系，设 \(f_i\) 为 \(i\) 层的答案，\(f_0=0,f_1=1\) ，对于 \(i>1\) 满足 \(f_i=2f_{i-2}+2\) 。

\(100\) 分做法：当 \(n\) 是偶数时，\(f_n=2^{n/2+1}-2\) ，当 \(n\) 是奇数时， \(f_n=2f_{n-1}-f_{n-3}\) 。

#include <bits/stdc++.h>
#define int long long 
using namespace std;

const int N=1.01e6,Mod=998244353;
int n,f[N];

int fpow(int x,int y){
    int z=1;
    while(y){
        if(y%2==1)z=x*z%Mod;
        x=x*x%Mod,y/=2;
    }
    return z;
}

int sol(int x){
    if(x%2==0)return (fpow(2,x/2+1)-2+Mod)%Mod;
    if(x==1)return 1;
    return (sol(x-1)*2-sol(x-3))%Mod;
}

signed main(){
    freopen("hanoi.in","r",stdin); 
    freopen("hanoi.out","w",stdout); 
    cin>>n;
    printf("%lld\n",sol(n));
    return 0;
}