二五语言

形式化题目

给定一个 $5 \times 5$ 的矩阵，在其中填入字符集合 $\{\text{'A'}, \text{'B'}, \dots, \text{'Y'}\}$ ，每个字符恰好出现一次。矩阵必须满足偏序约束：每一行从左至右严格递增，每一列从上至下严格递增。将矩阵按行优先顺序（从上到下、从左到右）展开得到的 25 字符字符串称为合法单词。所有合法单词按照字典序升序排列，编号从 1 开始。

任务为实现双向转换：

给定字典序排名，求对应的合法单词；
给定合法单词，求其字典序排名。

正解

思路

1. 杨表性质与状态空间

矩阵中的每行递增且每列递增，与组合数学中的**标准杨表（Standard Young Tableaux, SYT）**定义完全一致。

若我们按照字母从小到大（ $\text{'A'} \to \text{'B'} \to \dots \to \text{'Y'}$ ）的顺序依次将字母填入网格，任何时刻已经填入字母的格子所构成的图形必须是左上对齐的阶梯形（即杨图）。

设 5 行中各行已经填入的字符数分别为 $a, b, c, d, e$ 。由于每列递增，下方的行长度绝不能超过上方的行长度，因此状态必然满足约束：

5 \ge a \ge b \ge c \ge d \ge e \ge 0

这一状态空间的大小可以通过隔板法计算：

\binom{5 + 5}{5} = \binom{10}{5} = 252

所有可能达到的合法中间状态仅有 252 个。

2. 部分预填条件下的计数 DP

当部分格子已经确定了具体字符时，我们需要求出在满足这些预填约束下的合法填数方案数。

定义状态函数 dfs(a, b, c, d, e) 表示第 0 到 4 行分别已填入 $a, b, c, d, e$ 个字符时，填满整个网格的合法方案数。当前正要填入的字符编号为 $ch = a + b + c + d + e$ （ $0 \le ch < 25$ ）：

若 $ch = 25$ ，全部 25 个字符均已合法放入，返回 $1$ ；
否则，字符 $ch$ 只能放置在某行的末尾：
- 放至第 0 行第 $a$ 列：需满足 $a < 5$ 且位置 $(0, a)$ 未预填或预填字符恰为 $ch$ ；
- 放至第 1 行第 $b$ 列：需满足 $b < a$ 且位置 $(1, b)$ 未预填或预填字符恰为 $ch$ ；
- 放至第 2 行第 $c$ 列：需满足 $c < b$ 且位置 $(2, c)$ 未预填或预填字符恰为 $ch$ ；
- 放至第 3 行第 $d$ 列：需满足 $d < c$ 且位置 $(3, d)$ 未预填或预填字符恰为 $ch$ ；
- 放至第 4 行第 $e$ 列：需满足 $e < d$ 且位置 $(4, e)$ 未预填或预填字符恰为 $ch$ 。

将所有合法转移分支的方案数累加，并使用记忆化缓存，单次计算只需遍历最多 252 个状态。

3. 字典序逐位确定（数位 DP 思想）

单词由网格中位置 $0$ 到 $24$ （按行优先展开）的字符依次组成。我们从第 0 个格子到第 24 个格子依次确定字符：

根据排名求单词（模式 N）：从第 0 个格子开始，从小到大枚举尚未使用的字符 $ch$ 。在满足相邻偏序关系（不小于上方和左侧已填字符）的前提下，临时将该格子填为 $ch$ ，调用计数函数得到后续合法方案数 $ways$ 。
- 若 $ways \ge rank$ ，说明目标单词该位必为 $ch$ ，固定此字符并继续处理下一个格子；
- 若 $ways < rank$ ，说明目标单词还在后面，执行 $rank \leftarrow rank - ways$ ，并尝试下一个候选字符。
根据单词求排名（模式 W）：从第 0 个格子开始，设题目单词当前位置实际字符为 $target$ 。从小到大枚举未使用的字符 $ch < target$ ，若合法则计算当前尝试下的后续方案数并累加进总排名。之后将该位置固定为 $target$ ，继续处理下一位。最后总排名需加 1。

代码

Python 版：

python

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95#!/usr/bin/env python3
# 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-05-22 19:17
# update_at: 2026-05-22 19:17

import sys
from functools import cache

EMPTY = -1  # 棋盘格未填字母哨兵


def count_valid_grids(grid: list[list[int]]) -> int:
    """在当前已填部分限制下，计算合法的 5x5 标准杨表填充方案数。"""

    @cache
    def dfs(a: int, b: int, c: int, d: int, e: int) -> int:
        ch = a + b + c + d + e
        if ch == 25:
            return 1
        return (
            (dfs(a + 1, b, c, d, e) if a < 5 and grid[0][a] in (EMPTY, ch) else 0)
            + (dfs(a, b + 1, c, d, e) if b < a and grid[1][b] in (EMPTY, ch) else 0)
            + (dfs(a, b, c + 1, d, e) if c < b and grid[2][c] in (EMPTY, ch) else 0)
            + (dfs(a, b, c, d + 1, e) if d < c and grid[3][d] in (EMPTY, ch) else 0)
            + (dfs(a, b, c, d, e + 1) if e < d and grid[4][e] in (EMPTY, ch) else 0)
        )

    return dfs(0, 0, 0, 0, 0)


def encode_to_word(rank: int) -> str:
    """将排名 rank（从 1 开始）还原为对应的 25 字符单词。"""
    grid = [[EMPTY] * 5 for _ in range(5)]
    used = [False] * 25
    word: list[str] = []

    for i in range(25):
        r, c = divmod(i, 5)
        for ch in range(25):
            if used[ch]:
                continue
            if (r > 0 and grid[r - 1][c] > ch) or (c > 0 and grid[r][c - 1] > ch):
                continue
            grid[r][c] = ch
            ways = count_valid_grids(grid)
            if ways >= rank:
                used[ch] = True
                word.append(chr(ord("A") + ch))
                break
            rank -= ways
            grid[r][c] = EMPTY

    return "".join(word)


def word_to_encode(word: str) -> int:
    """将合法单词转换为其对应的排名编码（从 1 开始）。"""
    grid = [[EMPTY] * 5 for _ in range(5)]
    used = [False] * 25
    rank = 1

    for i, ch_char in enumerate(word):
        r, c = divmod(i, 5)
        target_ch = ord(ch_char) - ord("A")
        for ch in range(target_ch):
            if used[ch]:
                continue
            if (r > 0 and grid[r - 1][c] > ch) or (c > 0 and grid[r][c - 1] > ch):
                continue
            grid[r][c] = ch
            rank += count_valid_grids(grid)
            grid[r][c] = EMPTY
        grid[r][c] = target_ch
        used[target_ch] = True

    return rank


def solve() -> None:
    raw = sys.stdin.buffer.read()
    tokens = raw.split()
    mode = tokens[0].decode()

    if mode == "N":
        rank = int(tokens[1])
        print(encode_to_word(rank))
    else:
        word = tokens[1].decode()
        print(word_to_encode(word))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149/**
 * 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-10-06 13:15
 * update_at: 2026-10-06 13:18
 */
#include <cstdio>
#include <cstring>

typedef long long ll;

// 二五语言：合法单词等价于 5x5 标准杨表（每行每列递增）。
// 按字母 A..Y 从小到大依次填入时，已填格必为左上对齐的阶梯形，
// 用各行长度 (a,b,c,d,e) 即可完整描述一个中间状态（共 C(10,5)=252 个）。

const int EMPTY = -1;    // 棋盘格尚未填字母时的哨兵值
int board[5][5];         // board[r][c] 表示第 r 行第 c 列预填字母(0..24)，EMPTY 表示未填
ll memo[6][6][6][6][6];  // memo[a][b][c][d][e] 表示各行已填 a>=b>=c>=d>=e 个字母时的方案数

// 在 board 的预填约束下，计算把剩余字母继续按从小到大填满杨表的合法方案数。
// ch = a+b+c+d+e 是当前要放的字母，它只能落在某一行末尾。
ll dfs_count(int a, int b, int c, int d, int e) {
    int ch = a + b + c + d + e;
    if (ch == 25) {
        return 1;
    }
    if (memo[a][b][c][d][e] != -1) {
        return memo[a][b][c][d][e];
    }
    ll ways = 0;
    // 第 0~4 行：行尾格未预填或恰好预填 ch，才允许把当前字母放进去
    if (a < 5 && (board[0][a] == EMPTY || board[0][a] == ch)) {
        ways += dfs_count(a + 1, b, c, d, e);
    }
    if (b < a && (board[1][b] == EMPTY || board[1][b] == ch)) {
        ways += dfs_count(a, b + 1, c, d, e);
    }
    if (c < b && (board[2][c] == EMPTY || board[2][c] == ch)) {
        ways += dfs_count(a, b, c + 1, d, e);
    }
    if (d < c && (board[3][d] == EMPTY || board[3][d] == ch)) {
        ways += dfs_count(a, b, c, d + 1, e);
    }
    if (e < d && (board[4][e] == EMPTY || board[4][e] == ch)) {
        ways += dfs_count(a, b, c, d, e + 1);
    }
    memo[a][b][c][d][e] = ways;
    return ways;
}

// 清空记忆化并重新计算当前 board 约束下的方案总数
ll count_ways() {
    memset(memo, -1, sizeof(memo));
    return dfs_count(0, 0, 0, 0, 0);
}

// 模式 N：把排名 rank（从 1 开始）还原成对应的合法单词（字典序逐位确定）
void decode_rank(ll rank) {
    for (int r = 0; r < 5; r++) {
        for (int c = 0; c < 5; c++) {
            board[r][c] = EMPTY;
        }
    }
    bool used[25];
    memset(used, 0, sizeof(used));
    char word[30];

    for (int i = 0; i < 25; i++) {
        int r = i / 5;
        int c = i % 5;
        for (int ch = 0; ch < 25; ch++) {
            if (used[ch]) {
                continue;
            }
            // 当前位置必须大于上方和左方已填字母
            if (r > 0 && board[r - 1][c] > ch) {
                continue;
            }
            if (c > 0 && board[r][c - 1] > ch) {
                continue;
            }
            board[r][c] = ch;
            ll ways = count_ways();
            if (ways >= rank) {
                used[ch] = true;
                word[i] = 'A' + ch;
                break;
            }
            // 该位放 ch 时后面不足 rank 个单词，跳过这些单词继续试更大的字母
            rank -= ways;
            board[r][c] = EMPTY;
        }
    }
    word[25] = '\0';
    printf("%s\n", word);
}

// 模式 W：求合法单词的排名（从小到大累计更小字母可形成的方案数）
ll encode_word(const char *word) {
    for (int r = 0; r < 5; r++) {
        for (int c = 0; c < 5; c++) {
            board[r][c] = EMPTY;
        }
    }
    bool used[25];
    memset(used, 0, sizeof(used));

    ll rank = 1; // 字典序排名从 1 开始
    for (int i = 0; i < 25; i++) {
        int r = i / 5;
        int c = i % 5;
        int target = word[i] - 'A';
        for (int ch = 0; ch < target; ch++) {
            if (used[ch]) {
                continue;
            }
            if (r > 0 && board[r - 1][c] > ch) {
                continue;
            }
            if (c > 0 && board[r][c - 1] > ch) {
                continue;
            }
            board[r][c] = ch;
            rank += count_ways();
            board[r][c] = EMPTY;
        }
        board[r][c] = target;
        used[target] = true;
    }
    return rank;
}

int main() {
    char mode;
    if (scanf(" %c", &mode) != 1) {
        return 0;
    }
    if (mode == 'N') {
        ll rank;
        scanf("%lld", &rank);
        decode_rank(rank);
    } else {
        char word[30];
        scanf("%s", word);
        printf("%lld\n", encode_word(word));
    }
    return 0;
}

复杂度

时间复杂度：
- 网格共 25 个格子，每个格子尝试字符最多 25 种，单次查询中最多调用约 $25 \times 25 / 2 \approx 312$ 次计数 DP。
- 单次 DP 的状态数仅 $\binom{10}{5} = 252$ 个，每次转移为 $\mathcal{O}(1)$ 。
- 总运算量约在 $10^5$ 次操作以内，实际运行时间约为 $15 \sim 20\,\text{ms}$ ，远快于 $1000\,\text{ms}$ 的时限。
空间复杂度：
- 记忆化搜索状态数最多 252 个，递归栈深最多 25 层。
- 空间复杂度为 $\mathcal{O}(1)$ （常数级极小内存）。

总结

本题是标准杨表（SYT）与字典序逐位贪心计数的经典结合：

观察到行列递增的本质即为杨表，按数值从小到大填入时，已填图形必须保持非严格递减的阶梯状；
$5 \times 5$ 的阶梯形状数量仅有 $\binom{10}{5} = 252$ 个，状态空间极度收敛；
将预填字符作为转移过滤条件，把原问题转化为标准杨表上的动态规划计数与逐位试填。

图示解析

下图展示了字母按从小到大填入时，中间状态所必须遵循的杨图（Young diagram）阶梯结构：

graph TD
    subgraph 矩阵状态示例 (a=3, b=2, c=1, d=0, e=0)
        R0["行 0: [ A ][ B ][ C ] (a = 3)"]
        R1["行 1: [ D ][ E ]       (b = 2)"]
        R2["行 2: [ F ]             (c = 1)"]
        R3["行 3: (空)             (d = 0)"]
        R4["行 4: (空)             (e = 0)"]
    end
    R0 -->|限制| R1
    R1 -->|限制| R2
    R2 -->|限制| R3
    R3 -->|限制| R4

必须满足 $a \ge b \ge c \ge d \ge e$ ，下一个字符只能填在某行末尾，且新行的长度不能超过上一行，从而天然维护行列双向单调递增。

目录

形式化题目

正解

思路

1. 杨表性质与状态空间

2. 部分预填条件下的计数 DP

3. 字典序逐位确定（数位 DP 思想）

代码

复杂度

总结

图示解析