「A Decorative Fence」装饰围栏

形式化题目

求一个排列 $p_1,p_2,\dots,p_N$ ，它是长度分别为 $1,2,\dots,N$ 的 $N$ 块木板的某种排法，满足

\forall i \in [2, N-1]:\quad (p_i - p_{i-1})\cdot(p_{i+1} - p_i) < 0

即每个内部位置都是局部极值： $p_i$ 要么同时大于左右邻居（高位），要么同时小于（低位）。两端只有一侧邻居，不受这条约束。

把满足条件的排列按字典序排序，给定 $C$ ，求其中第 $C$ 个排列。

以 $N=3$ 为例， $3!=6$ 个排列中 1 2 3 与 3 2 1 是单调的、不合法，剩下 4 个按字典序排为 1 3 2、2 1 3、2 3 1、3 1 2，所以 $C=3$ 的答案是 2 3 1。

正解

思路

朴素做法： $N$ 块木板共 $N!$ 个排法，可以直接生成全部排列、筛出合法的再排序；也可以从字典序第 1 个出发，每次求"下一个合法排列"，走 $C-1$ 步。

两条路的瓶颈是同一个——它们只能一个一个地走：

做法	代价	$N=20$ 时
枚举全部排列	$O(N!)$	$20! \approx 2.4\times10^{18}$
只枚举合法排列	合法围栏总数	$740742376475050 \approx 7.4\times10^{14}$
从第 1 个逐个走到第 $C$ 个	$O(C)$	$C < 2^{63} \approx 9.2\times10^{18}$

要除掉这个瓶颈，就必须能直接算出"固定了某个前缀之后，后面还有多少种排法"，再用这些块大小一次跳过一整块——这正是"字典序第 $k$ 个排列"的标准通法。

观察一：字典序就是试填顺序。 木板长度互不相同，每个方案都是 $1..N$ 的一个排列，所以"先按 $p_1$ 升序、再按 $p_2$ 升序……"排出来的顺序就是字典序。于是可以一位一位地定：设当前要定第 $t$ 位，把候选值按升序试，如果第 $C$ 个不在"取这个值"的那一堆方案里，就整体跳过， $C$ 减去这一堆的方案数。

观察二：合法性只依赖相邻的大小关系，用不到具体数值。 交错条件只比较相邻两块的高低。枚举前缀时，后面能接什么只取决于两件事：当前这块在剩余板里的相对名次，以及它是高位还是低位。已经用掉了哪些具体长度不影响计数——只要还剩 $k$ 块板，把它们按大小重新编号成 $1..k$ ，当前板的名次是 $r$ ，问题就完全等价。

这一步把状态从"用掉的子集 + 具体端点值"压成了 $(k, r, \text{角色})$ 。定义

f(k,r,s)=\#\{\text{用 }1..k\text{ 排交错序列，首元素是第 }r\text{ 小，角色为 }s\text{ 的方案数}\}

其中 $s=\text{true}$ 表示首元素是高位（下一块必须更矮）， $s=\text{false}$ 表示低位（下一块必须更高）。

观察三： $f$ 可以自洽递推。 记第二块取的是第 $i$ 小，剥掉首元素后把剩下的 $k-1$ 块板重新编号：

$k=1$ ：只剩一块板，后面没有板要排， $f(1,1,s)=1$ ；
$k>1$ 且 $s=\text{true}$ ：第二块必须更矮，即 $i\in[1,r-1]$ ；被剥掉的首元素比第 $i$ 块高，所以第 $i$ 块重编号后名次不变：

f(k,r,\text{true})=\sum_{i=1}^{r-1} f(k-1,\,i,\,\text{false})

$k>1$ 且 $s=\text{false}$ ：第二块必须更高，即 $i\in[r+1,k]$ ；被剥掉的首元素比第 $i$ 块矮，所以第 $i$ 块重编号后名次减 1：

f(k,r,\text{false})=\sum_{i=r+1}^{k} f(k-1,\,i-1,\,\text{true})

两个分支角色都翻转，且都只依赖 $k-1$ 层，从 $k=1$ 往上算即可，没有循环依赖。

下表是 $f$ 的小规模取值：每个单元格里按 $r=1,2,\dots,k$ 的顺序列出该角色下的取值，也就是"处在这个状态时后面还能延伸出多少种排法"。

$k$	$s=\text{true}$ ， $r=1..k$	$s=\text{false}$ ， $r=1..k$	该 $k$ 的总方案数
1	1	1	—
2	0, 1	1, 0	2
3	0, 1, 1	1, 1, 0	4
4	0, 1, 2, 2	2, 2, 1, 0	10
5	0, 2, 4, 5, 5	5, 5, 4, 2, 0	32
6	0, 5, 10, 14, 16, 16	16, 16, 14, 10, 5, 0	122

把 $k\ge2$ 的每行两列全部相加，得到 $2,4,10,32,122,\dots$ ，正是各 $N$ 的合法围栏总数（ $N=4$ 时 10 种，与上面的清单一致），也解释了 $N=20$ 的总数 $740742376475050$ 从哪来。 $k=1$ 那一行要单独看：两种角色描述的是同一块板（只有一块板时没有邻居可比），所以 $N=1$ 的答案只有 1 种，而不是 $1+1=2$ 。

观察四：候选取值会被上一块收窄。 定第 $t$ 位（ $t>1$ ）时，上一块的角色已经确定，本块角色必须是它的反面，所以候选板只剩一段：

上一块是高位 → 本块必须更矮 → 只在剩余板中名次更小的那一段里试；
上一块是低位 → 本块必须更高 → 只在剩余板中名次更大的那一段里试。

代码里把还没用上的板按升序放在 avail 中，这一段就是连续的下标区间 avail[lo..hi]。

观察五：同一块板的两个角色有固定先后。 第一块没有前驱约束，两个角色都合法。以 $x$ 为第一块时，"高位"分支要求第二块 $<x$ ，"低位"分支要求第二块 $>x$ ，于是高位分支的每个排列都严格小于低位分支的每个排列。所以试填顺序是：先按板长升序，同一块板内部先数"高位"再数"低位"。

把五条观察合起来：

用 @cache 记忆化算出所有会用到的 $f(k,r,s)$ ，一次预处理，多组询问复用；
从左到右逐位确定：按试填顺序枚举候选 $(x,s)$ ，算出这一堆的大小 $f(k,\text{rank}(x),s)$ ； $C$ 大于它就整体跳过并让 $C$ 减去它，否则选中 $x$ ，把 $x$ 从 avail 移除、角色设为 $s$ 、候选区间收窄到 $x$ 的一侧，进入下一位。

以 $N=4,C=10$ （即该 $N$ 下的最后一个排列）为例，每一步的"跳过"都真实减掉了对应的方案数：

步	剩余板	试填板	角色	$f$	减去前的 $C$	结论
1	1 2 3 4	1	高位	0	10	跳过（ $f=0$ ， $C$ 不变）
1	1 2 3 4	1	低位	2	10	跳过 → $C=8$
1	1 2 3 4	2	高位	1	8	跳过 → $C=7$
1	1 2 3 4	2	低位	2	7	跳过 → $C=5$
1	1 2 3 4	3	高位	2	5	跳过 → $C=3$
1	1 2 3 4	3	低位	1	3	跳过 → $C=2$
1	1 2 3 4	4	高位	2	2	选中（ $2\leqslant2$ ）
2	1 2 3	1	低位	1	2	跳过 → $C=1$
2	1 2 3	2	低位	1	1	选中
3	1 3	3	高位	1	1	选中
4	1	1	低位	1	1	选中

得到 4 2 3 1。对照 $N=4$ 的全部 10 个合法围栏：

排名 $C$	1	2	3	4	5	6	7	8	9	10
围栏	`1 3 2 4`	`1 4 2 3`	`2 1 4 3`	`2 3 1 4`	`2 4 1 3`	`3 1 4 2`	`3 2 4 1`	`3 4 1 2`	`4 1 3 2`	`4 2 3 1`

最后一格正是上面的推演结果，说明"最后一个排列"确实排在最大排名上。

代码

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/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <cstdio>
using namespace std;

typedef long long ll;

const int MAXN = 22;

// way[k][rank][high]：k 块待排的板里，本块排第 rank 小、它是 high 位（1 高位 / 0 低位）时，
// 后面还有多少种排法。板长互不相同，「谁挨着谁」只由相对大小决定，所以剩下 k 块板的长度
// 可以重新编号成 1..k，rank 就是本块的编号——这是唯一需要的状态。
ll way[MAXN + 1][MAXN + 2][2];

ll n, c;
ll avail[MAXN + 2]; // 还没用上的板，长度升序存放；下标 i 就是第 i+1 小
int cnt;            // avail 里的板数
ll ans[MAXN + 2];
ll solved_cnt; // 本次询问实际填入的板数（无解时为 0，与 main.py 的空列表对齐）

void build_way() {
    way[1][1][0] = way[1][1][1] = 1; // 只剩本块，后面没有板，跳不跳都合法
    for (int k = 2; k <= MAXN; k++) {
        for (int rank = 1; rank <= k; rank++) {
            ll sum_high = 0, sum_low = 0;
            for (int r = 1; r < rank; r++) sum_high += way[k - 1][r][0]; // 高位块下一块必须更矮
            for (int r = rank + 1; r <= k; r++) sum_low += way[k - 1][r - 1][1]; // 低位块下一块必须更高
            way[k][rank][1] = sum_high;
            way[k][rank][0] = sum_low;
        }
    }
}

// 字典序第 c 个围栏：从左往右逐位试填，用「这一位取它时后面还有多少排法」整块跳过
void kth_fence() {
    cnt = n;
    for (ll i = 1; i <= n; i++) avail[i - 1] = i;
    ll high = -1;      // -1 表示本块是第一块，没有前一块来限制它
    ll lo = 0, hi = n - 1; // 本块的候选板在 avail 中的下标闭区间，由前一块的高低决定
    for (ll step = 0; step < n; step++) {
        ll k = cnt;
        for (ll idx = lo; idx <= hi; idx++) {
            // 试填顺序即字典序：候选板按长度升序，同一块板先数「它是高位」的方案（下一块更矮，更小）
            ll roles[2];
            int role_cnt;
            if (high < 0) {
                roles[0] = 1;
                roles[1] = 0;
                role_cnt = 2;
            } else {
                roles[0] = 1 - high; // 高低交错：角色与上一块相反
                role_cnt = 1;
            }
            int picked = 0;
            for (int t = 0; t < role_cnt; t++) {
                ll role = roles[t];
                ll ways = way[k][idx + 1][role];
                if (c > ways) {
                    c -= ways;
                    continue;
                }
                ans[solved_cnt] = avail[idx];
                solved_cnt += 1; // ★ 与 main.py 的 ans.append 对齐：计数 = 实际填入次数，不是 step+1
                                 //   （否则中途有空轮时 ans[] 留洞，输出残留 0）
                for (ll i = idx; i + 1 < cnt; i++) avail[i] = avail[i + 1]; // 删掉这块板
                cnt--;
                high = role;
                if (role == 1) {
                    lo = 0;
                    hi = idx - 1; // 高位块只配更矮的板
                } else {
                    lo = idx;
                    hi = k - 2; // 低位块只配更高的板（删掉后下标整体左移 1）
                }
                picked = 1;
                break;
            }
            if (picked) break;
        }
    }
}

int main() {
    build_way();
    ll cases;
    scanf("%lld", &cases);
    for (ll t = 0; t < cases; t++) {
        scanf("%lld%lld", &n, &c);
        solved_cnt = 0;
        kth_fence();
        // 与 main.py 对齐：无解（c 超过总方案数）时 ans 为空 ⇒ 输出空行
        for (ll i = 0; i < solved_cnt; i++) {
            if (i) printf(" ");
            printf("%lld", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

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#!/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-10-01 22:00
# update_at: 2026-10-01 22:00

import sys
from functools import cache


@cache
def suffixes(k: int, rank: int, high: bool) -> int:
    """k 块待排的板里，本块排第 rank 小、它是 high 位时，后面还有多少种排法。

    板长互不相同，"谁挨着谁"只由相对大小决定，所以剩下的 k 块板可以把长度重新
    编号成 1..k，rank 就是本块的编号——这是唯一需要的状态。角色只约束"下一块往
    哪跳"：高位板两侧都更低，下一块必须更矮；低位板两侧都更高，下一块必须更高。
    """
    if k == 1:
        return 1  # 只剩本块，后面没有板，跳不跳都合法
    if high:  # 下一块取第 1..rank-1 小，它在剥掉本块后仍是第 r 小
        return sum(suffixes(k - 1, r, False) for r in range(1, rank))
    return sum(suffixes(k - 1, r - 1, True) for r in range(rank + 1, k + 1))  # 本来更高的板，编号前移 1


def kth_fence(n: int, c: int) -> list[int]:
    """字典序第 c 个围栏：从左往右逐位试填，用"这一位取它时后面还有多少排法"整块跳过。"""
    avail = list(range(1, n + 1))  # 还没用上的板，长度升序；下标 i 就是第 i+1 小
    ans: list[int] = []
    high: bool | None = None  # None 表示本块是第一块，没有前一块来限制它
    lo, hi = 0, n - 1  # 本块的候选板在 avail 中的下标闭区间，由前一块的高低决定
    for _ in range(n):
        k = len(avail)
        roles = (True, False) if high is None else (not high,)  # 高低交错：角色与上一块相反
        # 试填顺序即字典序：候选板按长度升序，同一块板先数"它是高位"的方案（下一块更矮，更小）。
        for idx, role in ((idx, role) for idx in range(lo, hi + 1) for role in roles):
            ways = suffixes(k, idx + 1, role)
            if c > ways:  # 第 c 个落在这一块之后，整块跳过
                c -= ways
                continue
            ans.append(avail[idx])
            del avail[idx]
            high = role
            lo, hi = (0, idx - 1) if role else (idx, k - 2)  # 高位块只配更矮的板，低位块只配更高的板
            break
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    cases = next(data)  # 询问组数
    out: list[str] = []
    for _ in range(cases):
        n, c = next(data), next(data)  # 木板数、要求的排名
        out.append(' '.join(map(str, kth_fence(n, c))))
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

复杂度

时间： $f$ 的状态数为 $O(N^2)$ （ $k\leqslant N$ 、 $r\leqslant k$ 、两个角色），每个状态一次 $O(N)$ 求和，预处理 $O(N^3)$ ；之后每组询问逐位定位，每一位最多试填 $O(N)$ 个候选、共 $N$ 位， $O(N^2)$ 。 $N=20$ 时合计不到一万次加法，且与 $C$ 的大小无关。
空间：缓存 $O(N^2)$ 个计数（Python 原生大整数），加上 avail、ans 各 $O(N)$ 。
与代码对应：suffixes 就是 $f$ ，它的两个分支分别对应"下一块更矮"和"下一块更高"；kth_fence 是逐位定位，lo, hi 就是被上一块角色收窄的候选区间；solve 只负责读入、调用和输出。

总结

求字典序第 $k$ 个排列类问题的通法，是把"数数"和"定位"分开：先用一个只依赖相对大小的计数状态，算出"某一位取某个值时后面还有多少种排法"；再从左往右逐位试填，用这些块大小整块跳过，一遍就定位到答案。

本题的计数状态之所以能压到 $(k, r, \text{角色})$ ，关键在于交错条件只比较相邻两块的高低，因此"已经用掉了哪些具体长度"是无关信息——剩下的 $k$ 块板按大小重新编号成 $1..k$ 之后，问题完全等价。这也顺带保证了 $f$ 的取值范围只有 $7.4\times10^{14}$ 量级，Python 原生整数足够。

实现时有两个容易写错的地方：剥掉首元素后，比它高的板名次要减 1（代码中的 suffixes(k-1, r-1, True)）；以及第一块板没有前驱约束、两个角色都要试，且同一块板先数高位（下一块更矮的那一堆字典序在前）。

「A Decorative Fence」 装饰围栏

目录

形式化题目

正解

思路

代码

复杂度

总结

「A Decorative Fence」装饰围栏