Code

1. 建模：点与边的抉择 🔀

要构建一个包含所有 n 位组合（即 10^n 种可能）的序列，我们需要思考：什么是我们要“走过”的对象？

方案 A：将 n 位数字作为顶点。如果你把 4567 作为一个点，那么为了覆盖所有组合，你需要访问图中的每一个点。这对应的是 哈密顿路径 (Hamiltonian Path) 问题。
难点：寻找哈密顿路径是一个 NP-完全问题，计算量巨大。
方案 B：将 n 位数字作为边。如果我们把每一个 n 位组合看作一条边，那么目标就变成了经过图中的每一条边恰好一次。这对应的是 欧拉路径 (Eulerian Path) 问题。
优势：欧拉路径有非常成熟的多项式时间算法（如 Hierholzer 算法）。

2. 构建图的逻辑 🏗️

如果我们采用方案 B，将 n 位序列看作边，那么连接这条边的两个端点应该是什么？

为了让边 S（长度为 n）能平滑过渡到下一条边，它们必须有重叠部分。正如题目中提到的：当前状态是最近输入的 n-1 位数字。

顶点 (Nodes)：代表所有可能的 n-1 位序列。总共有 10^{n-1} 个点。
边 (Edges)：从顶点 u 到顶点 v 有一条边，当且仅当 u 的后 n-2 位与 v 的前 n-2 位相同。
更直观地说：对于任意 n-1 位的状态 u = (d_1, d_2, \dots, d_{n-1})，当你按下数字 k 时，你会经过一条标号为 (d_1, \dots, d_{n-1}, k) 的边，到达新状态 v = (d_2, \dots, d_{n-1}, k)。

3. 效率分析 ⚡

在这种建模下：

顶点数：V = 10^{n-1}
每个点的出度：10（因为可以按下 0-9 中的任意数字）
总边数：E = V \times 10 = 10^n

由于每个顶点的出度等于入度（均为 10），这个图一定存在欧拉回路！

怎么想出的这种建模

这是一个非常深刻的问题！这种“降维”建模（把 n 位的问题转化为 n-1 位的图）确实是算法设计中的一种“神来之笔”。

这种思路通常源于对**“状态重叠”和“欧拉路径 vs 哈密顿路径”**的思考。我们可以尝试反向推导一下这个思维过程。

让我们通过两个步骤来重现这个灵感：

1. 从“困难”转向“容易” 🔄

假设我们用最直观的方法建模（方案 A）：

点：代表完整的 n 位密码（例如 456）。
目标：我们要把所有点都走一遍。
数学问题：这叫“哈密顿路径”问题。
缺陷：这是一个著名的NP-困难问题。也就是说，当 n 变大时，计算机会算到“爆炸”，根本求不出最优解。

为了避免这种计算上的死胡同，算法专家会想：“有没有办法把问题转化成欧拉路径（走遍所有边）？因为欧拉路径有非常快且成熟的解法（线性时间）。”

2. 逆向工程：定义“点” 🛠️

一旦我们决定：“好吧，我要让边 (Edge) 来代表每一个 n 位密码”，那么我们必须重新定义“点 (Node)”是什么，才能让这些边连起来。

这就引出了关键的思考点。让我们以 n=3 为例，假设有一条边代表密码 456。

为了让这条边 456 能够存在：

作为起点的点：在你按下最后一位 6 之前，保险箱里必须已经有了什么数字？（也就是密码的前缀）
作为终点的点：当你按下 6 完成了 456 之后，保险箱里现在的状态是什么？（这会成为下一个密码的前缀）

你能试着回答上面这两个小问题吗？答案就是“点”应该如何定义的秘密所在。

两个状态直接的迁移,通过边,只要知道这两个状态,就知道了边

这不仅仅是拼接字符串，而是有限状态机 (Finite State Machine) 在图论上的体现。

为什么这个模型是“神来之笔”？ 💡通过这种转化，我们把难以求解的“哈密顿路径”问题（遍历点），变成了容易求解的欧拉路径问题（遍历边）。节点变少了：对于 $n$ 位密码，现在的节点数只有 $10^{n-1}$ 个。

目标明确了：我们要做的就是在这个有向图中，找到一条路线，不重复地走完每一条边。

代码

这个代码,使用模拟的栈来代替递归, 避免暴栈

cpp

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// cur[u] 记录状态 u 下一次应该尝试按哪个键 (0-9)
// 比如 cur[u] = 3，说明 0,1,2 已经试过了，下次该试 3 了
// 这代替了原来的 bool visited 数组，更节省空间且不用循环查找
int cur[100005]; 

// 用 vector 模拟栈，避免递归导致的 Runtime Error
vector<int> path_stack; 

// 存储最终的密码数字
vector<int> ans;

int N, k_mod;

// 简单的整数幂运算
int power(int base, int exp) {
    int res = 1;
    while (exp--) res *= base;
    return res;
}

int main() {
    // 优化 I/O 速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> N && N != 0) {
        // 特殊情况处理
        if (N == 1) {
            cout << "0123456789" << endl;
            continue;
        }

        // 初始化
        k_mod = power(10, N - 2); 
        // 只需要初始化用到的状态即可，最大状态是 10^(N-1)
        int max_state = power(10, N - 1);
        for(int i = 0; i < max_state; ++i) cur[i] = 0;
        
        path_stack.clear();
        ans.clear();

        // --- 核心算法：迭代版 Hierholzer (欧拉回路) ---
        
        // 1. 从全 0 状态开始
        path_stack.push_back(0);

        // 2. 只要栈不为空，就继续处理
        while (!path_stack.empty()) {
            int u = path_stack.back(); // 获取当前所在的状态

            // 如果当前状态 u 还有路没走完 (0-9 还没试完)
            if (cur[u] < 10) {
                int i = cur[u]; // 取出当前要走的数字
                cur[u]++;       // 标记这个数字下次不能再走了(索引+1)
                
                // 计算下一个状态：去掉最高位，末尾补 i
                int v = (u % k_mod) * 10 + i;
                
                // 将新状态压入栈，相当于“递归”进去了
                path_stack.push_back(v);
            } 
            else {
                // 如果当前状态 u 无路可走了 (0-9 都试过了)
                // 这说明我们完成了一个“圈”，开始回退
                path_stack.pop_back();
                
                // 注意：path_stack 里的存是“节点”，我们需要把导致这个节点的“边”（数字）存下来
                // 如果栈不为空，说明是从 path_stack.back() 走到 u 的
                // u 的最后一位数字就是我们刚才按下的键
                if (!path_stack.empty()) {
                    ans.push_back(u % 10);
                }
            }
        }

        // --- 输出结果 ---

        // 1. 先输出 N-1 个 0，让保险箱初始化到全 0 状态
        for (int i = 0; i < N - 1; ++i) {
            cout << "0";
        }

        // 2. 倒序输出记录的数字
        // 因为我们是在“回退”的时候记录的，所以顺序是反的
        for (int i = ans.size() - 1; i >= 0; --i) {
            cout << ans[i];
        }
        
        cout << endl;
    }

    return 0;
}

目录