有趣的数

形式化题目

统计长度恰为 $n$ 的数字串：只用 0、1、2、3，四个数字都至少出现一次，所有 0 都在所有 1 前，所有 2 都在所有 3 前，且首位不能为 0。每组答案对 $10^9+7$ 取模。

思路

先看按位选择数字的递归写法：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:48
 */
// brute.cpp：按位递归枚举四种数字，并缓存重复的后缀状态。
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

int n;
long long memo[1002][3][3];

long long dfs(int pos, int first, int second) {
    if (pos > n) {
        return first == 2 && second == 2;
    }

    if (memo[pos][first][second] != -1) {
        return memo[pos][first][second];
    }

    long long ways = 0;
    // 追加 0：还没有出现 1 时才允许。
    if (first < 2) {
        ways += dfs(pos + 1, max(first, 1), second);
    }
    // 追加 1：必须已经出现过 0。
    if (first > 0) {
        ways += dfs(pos + 1, 2, second);
    }

    // 追加 2：还没有出现 3 时才允许。
    if (second < 2) {
        ways += dfs(pos + 1, first, max(second, 1));
    }
    // 追加 3：必须已经出现过 2。
    if (second > 0) {
        ways += dfs(pos + 1, first, 2);
    }

    memo[pos][first][second] = ways % MOD;
    return memo[pos][first][second];
}

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

    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        memset(memo, -1, sizeof(memo));

        // 首位只能是 2，因此从第二位开始枚举。
        cout << dfs(2, 0, 1) << '\n';
    }

    return 0;
}

首位不可能是 0、1、3，所以只能固定为 2。从第二位起，每层尝试追加四个数字，并检查是否违反两个先后关系。去掉记忆化时，这棵搜索树规模为 $O(4^{n-1})$ ；代码保留递归选择结构，并缓存重复的后缀阶段，使官方的大样例也能验证。

压缩状态

关键是完整前缀并不重要。对 0/1 定义三态 a：0 表示未出现 0，1 表示已经出现 0 但没有 1，2 表示已经出现 1。对 2/3 同样定义三态 b。于是只有 $3\times3=9$ 个状态。

令 dp[len][a][b] 表示长度为 len 的合法前缀数，初始值为 dp[1][0][1]=1。从 (a,b) 出发：

a<2 时追加 0，转移到 (max(a,1),b)；a>0 时追加 1，转移到 (2,b)。
b<2 时追加 2，转移到 (a,max(b,1))；b>0 时追加 3，转移到 (a,2)。

答案是 dp[n][2][2]，因为两个阶段都到 2 才表示四种数字全部出现。

三态 DP 样例表

下表展示从长度 1 到 4 时 9 个状态的方案数；(a,b) 分别表示 0/1 与 2/3 的阶段，取值依次是“未出现前者、只出现过前者、已出现后者”。

状态 `(a,b)`	长度 1	长度 2	长度 3	长度 4
(0, 0)	0	0	0	0
(0, 1)	1	1	1	1
(0, 2)	0	1	2	3
(1, 0)	0	0	0	0
(1, 1)	0	1	3	7
(1, 2)	0	0	2	9
(2, 0)	0	0	0	0
(2, 1)	0	0	1	5
(2, 2)	0	0	0	3

长度 1 时只有单个数字 2，所以只有 (0,1) 为 1。长度 4 时目标状态 (2,2) 为 3，正好得到 2013、2031、2301。每一列由前一列四种追加数字累积而来，展示了状态而非具体前缀足以完成计数。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:48
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
const long long MOD = 1000000007LL;

long long dp[MAXN + 1][3][3];

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

    // 首位不能是 0，而合法数的首位只能是 2。
    dp[1][0][1] = 1;

    for (int len = 1; len < MAXN; len++) {
        for (int first = 0; first < 3; first++) {
            for (int second = 0; second < 3; second++) {
                long long ways = dp[len][first][second];
                if (ways == 0) {
                    continue;
                }

                // 状态 first：0 未出现 0，1 已有 0 但没有 1，2 已出现 1。
                if (first < 2) {
                    int next_first = max(first, 1);
                    dp[len + 1][next_first][second] += ways;
                    dp[len + 1][next_first][second] %= MOD;
                }
                if (first > 0) {
                    dp[len + 1][2][second] += ways;
                    dp[len + 1][2][second] %= MOD;
                }

                // 状态 second：0 未出现 2，1 已有 2 但没有 3，2 已出现 3。
                if (second < 2) {
                    int next_second = max(second, 1);
                    dp[len + 1][first][next_second] += ways;
                    dp[len + 1][first][next_second] %= MOD;
                }
                if (second > 0) {
                    dp[len + 1][first][2] += ways;
                    dp[len + 1][first][2] %= MOD;
                }
            }
        }
    }

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << dp[n][2][2] << '\n';
    }

    return 0;
}

复杂度

预处理 $1000\times3\times3$ 个状态，每个状态最多有四条转移，时间复杂度为 $O(1000)$ ；回答询问额外为 $O(T)$ 。dp 数组空间复杂度为 $O(1000)$ 。

总结

先后限制常常不需要记录完整前缀，只要记录“是否已经进入后一阶段”。把两对数字各压缩为三态后，指数级的数字选择树就变成了只有 9 个状态的计数 DP。

图示解析

这张图串起本题从数字限制到计数答案的主线：

text

1
2
3
4
5
6所有 0 在 1 前，所有 2 在 3 前
`- 每一对数字压缩成三个阶段
   |- 0/1 的阶段 a
   `- 2/3 的阶段 b
      `- 首位固定为 2，从状态 (0, 1) 开始
         `- 逐位追加四种合法数字，转移到 dp[n][2][2]

状态只记录“是否已经跨过 1”与“是否已经跨过 3”，不需要记录完整前缀。两组阶段的组合只有 $3\times3=9$ 种，长度增加一位时只做常数次转移。最终 (2,2) 同时保证四个数字都出现过，并满足两个先后限制。

目录

形式化题目

思路

压缩状态

三态 DP 样例表

代码

复杂度

总结

图示解析