拉丁正方形

形式化题目

给定正整数 $N$ （ $2 \le N \le 7$ ）。求满足下列条件的 $N \times N$ 矩阵 $A$ 的总数：

每个元素 $A_{i,j} \in \{1, 2, \dots, N\}$ ；
每行、每列均是 $\{1, 2, \dots, N\}$ 的一个置换（即 $A$ 是一个 $N$ 阶拉丁方阵）；
第一行固定为 $A_{1, j} = j$ （ $1 \le j \le N$ ）。

题目解析

思路

直接从上到下、逐格尝试填数是经典的爆搜思路。但当 $N = 7$ 时，合法的拉丁方阵数量超过百亿，单纯剪枝也难以在时限内跑出结果。我们需要利用题目的对称性大幅压缩搜索状态。

1. 归约为标准型拉丁方阵（Reduced Latin Square）

一个第一行和第一列均为 $(1, 2, \dots, N)$ 的拉丁方阵称为标准型拉丁方阵。

题目只固定了第一行为 $(1, 2, \dots, N)$ ，对第一列没有限制。但在任意合法方阵中，第一列的各元素必定是 $\{1, 2, \dots, N\}$ 的一个排列。由于第一行第一列的元素已确定为 $1$ ，第 $2 \dots N$ 行在第一列上的元素必然是 $\{2, 3, \dots, N\}$ 的某种全排列。

如果我们对方阵的第 $2 \sim N$ 行按其第一列元素的大小进行重排：

第一行未参与重排，仍保持 $(1, 2, \dots, N)$ ；
第一列排序后变为 $(1, 2, \dots, N)$ ；
行与列的唯一性性质在行置换下完全保持。

这意味着：每一个标准型拉丁方阵，通过对后 $N-1$ 行进行任意排列，都能唯一生成一个符合题意的方阵。后 $N-1$ 行共有 $(N-1)!$ 种置换方式，因此：

\text{答案} = (N-1)! \times (\text{标准型拉丁方阵总数 } R_N)

当 $N=7$ 时， $(7-1)! = 720$ ，此步骤直接将计算量压缩了 $720$ 倍。

2. 第二行置换环同构剪枝

在标准型拉丁方阵中，第一行与第一列均已固定为 $(1, 2, \dots, N)$ 。此时考虑第二行：

其首项固定为 $2$ ；
其余第 $2 \dots N$ 项填入 $\{1, 3, 4, \dots, N\}$ 的一个排列，且对于每个位置 $c \ge 2$ ，填入的数值不能等于 $c$ （不能与第一行同列元素冲突）。

将第二行看作一个将位置映射到数值的置换：任意一个置换都可以唯一分解为若干个互不相交的轮换（置换环）。由于同时置换后续的行标、列标和数值符号保持拉丁方阵的结构不变，只要两个第二行排列的置换环长度多重集相同，它们后续能够填出的合法方阵数就完全相等。

以 $N=7$ 为例，合法的第二行排列有 $1853$ 个，但它们的置换环长度多重集仅有以下 $4$ 种：

环长结构类型	出现次数	后续方案数（代表元搜索结果）
$(2, 2, 3)$	$35$	$55296$
$(2, 5)$	$84$	$55040$
$(3, 4)$	$70$	$54528$
$(7)$	$120$	$54720$

因此，我们无需对所有排列都执行深度优先搜索，只需要：

枚举合法的第二行排列，按环结构分类计数；
对每种类型只选出一个代表排列，运行一次位运算回溯搜索；
将搜索结果乘上该类型的频次后累加，即可得到 $R_N$ 。

在位运算 DFS 中，维护每一行与每一列已填数值的二进制掩码，每次利用 avail & -avail 快速枚举可行数字填入下一格，搜索极其高效。

flowchart TD
    A["固定第 1 行与第 1 列 (标准型)"] --> B["枚举第 2 行合法错排"]
    B --> C["分解置换环，归入等价类"]
    C --> D["对各类代表元执行位运算 DFS"]
    D --> E["方案数加权求和得到 R_N"]
    E --> F["答案 = R_N * (N-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#!/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-07-05 21:47
# update_at: 2026-07-05 21:47

import itertools
import math
import sys


def count_completions(n: int, p: tuple[int, ...]) -> int:
    """计算第 2 行固定为 p 时，剩余单元格的合法填充方案数。"""
    all_mask = (1 << n) - 1
    row_mask = [1 << r for r in range(n)]
    col_mask = [1 << c for c in range(n)]
    row_mask[0] = col_mask[0] = all_mask  # 第 1 行与第 1 列各填满了 0..n-1

    for c, v in enumerate(p, 1):
        row_mask[1] |= 1 << v
        col_mask[c] |= 1 << v

    def dfs(r: int, c: int) -> int:
        if r == n - 1:
            return 1
        nr, nc = (r, c + 1) if c + 1 < n else (r + 1, 1)
        avail = all_mask & ~(row_mask[r] | col_mask[c])
        cnt = 0
        while avail:
            low = avail & -avail
            avail ^= low
            row_mask[r] |= low
            col_mask[c] |= low
            cnt += dfs(nr, nc)
            row_mask[r] ^= low
            col_mask[c] ^= low
        return cnt

    return dfs(2, 1)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)
    except StopIteration:
        return
    if n <= 2:
        print(1)
        return

    rem = [0] + list(range(2, n))
    types: dict[tuple[int, ...], tuple[tuple[int, ...], int]] = {}

    for p in itertools.permutations(rem):
        if any(c == v for c, v in enumerate(p, 1)):
            continue
        full_p = (1, *p)
        vis, cycles = [False] * n, []
        for i in range(n):
            if not vis[i]:
                cur, length = i, 0
                while not vis[cur]:
                    vis[cur] = True
                    cur = full_p[cur]
                    length += 1
                cycles.append(length)
        key = tuple(sorted(cycles))
        types[key] = (p, types.get(key, (p, 0))[1] + 1)

    reduced_count = sum(count_completions(n, rep) * cnt for rep, cnt in types.values())
    print(reduced_count * math.factorial(n - 1))


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
150
151
152/**
 * 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-04 22:30
 * update_at: 2026-10-06 12:28
 */
// 思路（对应 index.md）：
// 1. 只固定第一行的拉丁方阵，可以把第 2..N 行按第一列排序归约为标准型，
//    所以 答案 = 标准型数量 R_N * (N-1)!。
// 2. 标准型中第二行是一个错排置换，把行、列、数值做同样的重标后，
//    环长多重集相同的第二行给出的后续方案数相同，按环结构等价类合并，
//    每类只跑一次位运算 DFS。

#include <cstdio>
#include <algorithm>
typedef long long ll;

const int MAXN = 8;

int n;                       // 题目给的 N
int all_mask;                // (1<<n)-1，表示 0..n-1 全部数字的掩码
int row_mask[MAXN];          // row_mask[r]：第 r 行已出现数字的位掩码
int col_mask[MAXN];          // col_mask[c]：第 c 列已出现数字的位掩码
int second_row[MAXN];        // 当前枚举的第二行（0 下标存列 0 的值 1）
bool vis[MAXN];              // 置换环分解时的访问标记
int cycle_len[MAXN];         // 分解出的环长
int cycle_cnt;               // 环的个数

// 等价类合并用：环长多重集相同的第二行归为一类
struct CycleType {
    int len[MAXN];       // 排序后的环长
    int num_cycles;      // 环的个数
    int count;           // 该等价类中合法第二行排列的个数
    int rep[MAXN];       // 一个代表元
};
CycleType types[1000];       // 第二行合法排列至多 720 个，等价类远少于此
int type_num;

// 把当前 second_row 当作置换 p（p[i] = 第 i 列的值），分解环长多重集
void decompose_cycles() {
    for (int i = 0; i < n; i++) vis[i] = false;
    cycle_cnt = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        int length = 0;
        int cur = i;
        while (!vis[cur]) {
            vis[cur] = true;
            cur = second_row[cur];
            length++;
        }
        cycle_len[cycle_cnt++] = length;
    }
    std::sort(cycle_len, cycle_len + cycle_cnt);
}

// 比较两个环长多重集是否相同
bool same_cycles(const CycleType &a, int *b, int cnt) {
    if (a.num_cycles != cnt) return false;
    for (int i = 0; i < cnt; i++)
        if (a.len[i] != b[i]) return false;
    return true;
}

// 搜索（r, c）之后所有格子的填法数，位运算枚举可行数字
// 剩余格子从第 2 行第 1 列开始（下标从 0 起，第 0 行、第 0 列已固定）
ll dfs(int r, int c) {
    if (r == n - 1) return 1;          // 只剩最后一行时它已被唯一确定
    int nr = r, nc = c + 1;
    if (nc == n) { nr++; nc = 1; }     // 换行，第 0 列已由第一列固定跳过
    ll res = 0;
    int avail = all_mask & ~(row_mask[r] | col_mask[c]);
    while (avail) {
        int low = avail & (-avail);    // 取最低位的可行数字
        avail ^= low;
        row_mask[r] |= low;
        col_mask[c] |= low;
        res += dfs(nr, nc);
        row_mask[r] ^= low;
        col_mask[c] ^= low;
    }
    return res;
}

// 固定第二行为 perm，统计标准型方阵的完成数
ll count_completions(int *perm) {
    all_mask = (1 << n) - 1;
    // 初始时第 r 行已含第一列的值 r，第 c 列已含第一行的值 c（0 下标）
    for (int i = 0; i < n; i++) {
        row_mask[i] = 1 << i;
        col_mask[i] = 1 << i;
    }
    row_mask[0] = all_mask;            // 第一行 0..n-1 全部出现
    col_mask[0] = all_mask;            // 第一列 0..n-1 全部出现
    for (int c = 1; c < n; c++) {
        row_mask[1] |= 1 << perm[c];
        col_mask[c] |= 1 << perm[c];
    }
    return dfs(2, 1);
}

int main() {
    if (scanf("%d", &n) != 1) return 0;

    if (n == 2) {                      // N=2 时标准型只有 1 个
        printf("1\n");
        return 0;
    }

    // 枚举第二行第 1..n-1 列的错排：0 下标下第二行是 0,2,3..n-1 的排列，列 0 固定为 1
    int rest[MAXN], rest_num = 0;
    rest[rest_num++] = 0;
    for (int v = 2; v < n; v++) rest[rest_num++] = v;
    std::sort(rest, rest + rest_num);
    do {
        // 检查错排：第 c 列的值不能等于 c（0 下标，列 1..n-1 对应 rest 的 0..rest_num-1）
        bool ok = true;
        for (int i = 0; i < rest_num && ok; i++)
            if (rest[i] == i + 1) ok = false;
        if (!ok) continue;

        second_row[0] = 1;
        for (int c = 1; c < n; c++) second_row[c] = rest[c - 1];

        // 分解置换环，按环长多重集归入等价类
        decompose_cycles();
        int found = -1;
        for (int t = 0; t < type_num; t++)
            if (same_cycles(types[t], cycle_len, cycle_cnt)) { found = t; break; }
        if (found == -1) {             // 新的环结构类型
            found = type_num++;
            types[found].count = 0;
            types[found].num_cycles = cycle_cnt;
            for (int i = 0; i < cycle_cnt; i++) types[found].len[i] = cycle_len[i];
        }
        types[found].count++;          // 该等价类的排列个数加一
        if (types[found].count == 1)   // 第一个遇到的作为代表元
            for (int i = 0; i < n; i++) types[found].rep[i] = second_row[i];
    } while (std::next_permutation(rest, rest + rest_num));

    // 对每个等价类的代表元跑一次位运算 DFS，加权求和得 R_N
    ll reduced = 0;
    for (int t = 0; t < type_num; t++)
        reduced += count_completions(types[t].rep) * (ll)types[t].count;

    // 答案 = R_N * (N-1)!
    ll factor = 1;
    for (int i = 2; i <= n - 1; i++) factor *= i;
    printf("%lld\n", reduced * factor);
    return 0;
}

复杂度分析

时间复杂度：
- 第二行全排列的枚举量最多为 $(N-1)! \le 6! = 720$ 种，环分解耗时在数毫秒内。
- 对于 $N \le 7$ ，等价类最多仅 $4$ 种，位运算 DFS 只需执行 $4$ 次，总搜索节点数很少，总运行时间约 $0.6$ 秒，远低于 $1000\text{ ms}$ 时限。
空间复杂度：
- 递归调用深度为网格剩余格子数，至多不超过 $N^2 \le 49$ 层。
- 仅需维护长度为 $N$ 的整型位掩码数组，空间复杂度为 $\mathcal{O}(N)$ ，内存占用极小。

目录

形式化题目

题目解析

思路

1. 归约为标准型拉丁方阵（Reduced Latin Square）

2. 第二行置换环同构剪枝

代码

复杂度分析