题解 | #汉诺塔#

C. 汉诺塔

知识点：递归、递推、取模

设 表示 个圆盘的普通版汉诺塔的最小步数。

有递推式 f[0] = 0, f[i] = 2 * f[i-1] + 1。

通过数学方法或找规律易得 f[n] = 2^n – 1

假设最大的圆盘在2号柱子上，那么可以分为三步：

1. 把别的盘子整齐地叠到1号柱子上
2. 把最大的盘子从2号柱子移到3号柱子
3. 把1号柱子上的所有盘子移到3号柱子上

2、3 两步的步数可以用上面的经典版汉诺塔步数公式计算出来。

于是问题变成了把剩下的 个盘子移到1号柱子上需要多少步。

可以使用递归的方法解决，不用递归用循环也是可以的。

标程

C++

递归版

#include <iostream>

using namespace std;

using ll = long long;

constexpr int N = 200000 + 9, mod = 1'000'000'007;

int n;
int f[N];
int a[N];

ll hanoi(int step, int target)
{
    if (step == n)
        return 0;
    ll res = 0;
    if (a[step] != target)
    {
        res += hanoi(step + 1, target ^ a[step]); // target ^ a[step] 表示 1, 2, 3 中除了 target 和 a[step] 之外的那个柱子
        res += f[n - step - 1] + 1;
    }
    else
    {
        res += hanoi(step + 1, target);
    }
    return res % mod;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    f[0] = 0;
    for (int i = 1; i < n; ++i)
    {
        f[i] = (2 * f[i - 1] + 1) % mod;
    }
    ll ans = hanoi(0, 3);
    cout << ans << '\n';
}

循环版

#include <bits/stdc++.h>

using namespace std;

constexpr int mod = 1'000'000'007;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int target = 3;
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        ans *= 2;
        if (x != target)
        {
            ans += 1;
            target ^= x; // 将 target 赋值为 1, 2, 3 三个数中除了 target 和 x 之外的那个数
        }
        ans %= mod;
    }
    cout << ans << '\n';
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static Kattio io = new Kattio();

    final static int mod = 1000000007;
    public static void main(String[] args) {
        int n;
        n = io.nextInt();
        int target = 3;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int x;
            x = io.nextInt();
            ans *= 2;
            if (x != target) {
                ans += 1;
                target ^= x;
            }
            ans %= mod;
        }
        io.println(ans);

        io.close();
    }
}

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;
    // 标准 IO
    public Kattio() { this(System.in, System.out); }
    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }
    // 在没有其他输入时返回 null
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {}
        return null;
    }
    public int nextInt() { return Integer.parseInt(next()); }
    public double nextDouble() { return Double.parseDouble(next()); }
    public long nextLong() { return Long.parseLong(next()); }
}

Python

mod = 10**9 + 7

n = int(input())
a = list(map(int, input().split()))

target = 3
ans = 0
for x in a:
    ans *= 2
    if x != target:
        ans += 1
        target = 6 - target - x
    ans %= mod
print(ans)