交换

GitHub跳转原题关系图返回列表

从恒等排列出发按 q 的顺序做 n-1 次相邻交换,倒着钦定每个区间最后使用的边,左块值域必须对齐,两段操作可自由交错,答案由区间 DP 乘组合数归并系数得到。

OJ: roj

题目 ID: 1768

难度:提高+/省选-

标签:动态规划区间DP组合数学python

创建: 2026-10-08 01:05

更新: 2026-10-08 01:05

形式化题目

给定 nn 与一个 {0,1,…,n−1}\{0, 1, \dots, n-1\} 的排列 pp。称 {0,1,…,n−2}\{0, 1, \dots, n-2\} 的排列 q=(q0,q1,…,qn−2)q = (q_0, q_1, \dots, q_{n-2}) 是优美的,当且仅当:从 s=(0,1,…,n−1)s = (0, 1, \dots, n-1) 出发, 对 i=0,1,…,n−2i = 0, 1, \dots, n-2 依次执行"交换 s[qi]s[q_i] 与 s[qi+1]s[q_i+1]",n−1n-1 次之后恰好得到 s=ps = p。求优美排列 qq 的个数,对 109+710^9+7 取模。

qq 是 {0,…,n−2}\{0, \dots, n-2\} 的一个全排列,所以每条相邻边 (i,i+1)(i, i+1) 在整个过程中 恰好被使用一次。这是全题唯一的入口条件,把它翻译成一句人话就是:

每个数只允许朝一个方向平移——它一旦跨过边 (i,i+1)(i, i+1),这条边就用掉了, 而边不可重复使用,它再也回不来。

样例 n=3n = 3,p=(1,2,0)p = (1, 2, 0):q=(0,1)q = (0, 1) 时 (0,1,2)→(1,0,2)→(1,2,0)(0,1,2) \to (1,0,2) \to (1,2,0) 成功; q=(1,0)q = (1, 0) 时 (0,1,2)→(0,2,1)→(2,0,1)(0,1,2) \to (0,2,1) \to (2,0,1) 失败。故答案为 11。

正解

思路

朴素做法。 枚举 qq 的全部 (n−1)!(n-1)! 种排列,每种正向模拟 n−1n-1 次交换,与 pp 比对。 n≤50n \le 50 时 49!≈6.1×106249! \approx 6.1 \times 10^{62},没有任何剪枝能救。30% 的 n≤10n \le 10 可以这样拿分((9)!=362880(9)! = 362880,实测秒过),但满分必须换思路。

突破口:倒着想。 正向是"按时间顺序放边",qq 的 n−1n-1 个位置互相纠缠; 但"每条边恰好用一次"这个条件在时间轴上是对称的,于是可以倒过来问:

在区间 [L,R][L, R] 内,最后一条被使用的边是哪一条?

设这条边是 kk,它交换位置 kk 与 k+1k+1。关键观察是交换完之后,位置 kk 右侧的边 (k+1,k+2),…(k+1, k+2), \dots 还都没用,但它们只会影响位置 ≥k+1\ge k+1 的数;同理左侧。 换句话说:

交换边 kk 的那一刻,左块 [L,k][L, k] 里的数再也不可能跑到右块去,反之亦然。

所以交换之前左块 [L,k][L, k] 里站着的必须已经是 {L,L+1,…,k}\{L, L+1, \dots, k\} 这 k−L+1k-L+1 个数 (值域对齐),否则交换后总有数留在错误的一侧。这条约束一旦满足,左右两块从此 完全解耦,各自变成独立子问题——这正是区间 DP 的形状。

子问题的内容长什么样? 直接把"区间内每个位置站着哪个数"作为状态是 O(n!)O(n!) 的。 这里要用一个结构性事实:设祖先的交换把两个外来数推到了区间 [L,R][L, R] 的两个端点上, 那么

c[L..R]=[x,  p[L+1],  p[L+2],  …,  p[R−1],  y],c[L..R] = \bigl[x,\; p[L+1],\; p[L+2],\; \dots,\; p[R-1],\; y\bigr],

即区间内部位置 jj 上的值恒等于 p[j]p[j],只有两个端点可能是被推进来的外来数。 理由是区间内部的每个位置都只被本区间内的交换碰过,它最终停在哪就是 pp 里的位置; 而端点是跨越区间边界的那次交换留下来的。又因为区间内容必须是 {L..R}\{L..R\} 的一个排列, yy 由 xx 与内部值唯一确定(就是剩下没出现的那个数)。于是状态只需 O(n3)O(n^3) 个:(L,R,x)(L, R, x)。

转移。 设 f(L,R,x)f(L, R, x) 为区间 [L,R][L, R] 的内容左端点是 xx 时的方案数。枚举最后 一条边 k∈[L,R−1]k \in [L, R-1],把区间内容 cc 的 kk、k+1k+1 两格交换得到 AA,要求

A[L], A[L+1], …, A[k]恰好是{L,L+1,…,k},A[L] ,\, A[L+1] ,\, \dots ,\, A[k] \quad\text{恰好是}\quad \{L, L+1, \dots, k\},

即交换后左块 A[L..k]A[L..k] 的值域对齐:A[L..k]=c[L..k−1]∪{c[k+1]}A[L..k] = c[L..k-1] \cup \{c[k+1]\}(只有两格 c[k]c[k]、c[k+1]c[k+1] 换了位),这 k−L+1k-L+1 个数必须正好填满 [L,k][L, k]。此时交换后左块是 [L,k][L, k]、右块是 [k+1,R][k+1, R],各自递归。 余下的 R−L−1R-L-1 条边中,左子区间占 k−Lk-L 条、右子区间占 R−k−1R-k-1 条,两段互不干涉, 可以任意交错,交错方案数是组合数 (R−L−1k−L)\dbinom{R-L-1}{k-L}。因此

f(L,R,c)=∑k 合法(R−L−1k−L)⋅f(L,k,A[L])⋅f(k+1,R,A[k+1]).f(L, R, c) = \sum_{k \text{ 合法}} \binom{R-L-1}{k-L} \cdot f\bigl(L, k, A[L]\bigr) \cdot f\bigl(k+1, R, A[k+1]\bigr).

边界 f(L,L,c)=[c[L]=L]f(L, L, c) = [c[L] = L]。答案即 f(0,n−1,p[0])f(0, n-1, p[0])(初始区间内容是整个 pp)。

验证样例 n=5n=5、p=(3,0,1,4,2)p=(3,0,1,4,2)(本题第 6 个测试点,答案 33)。 根区间 [0,4][0,4] 内容为 c=(3,0,1,4,2)c=(3,0,1,4,2),枚举最后一条边 kk(交换 cc 的 kk、k+1k+1 两格后 左块是 A[0..k]A[0..k]):

最后一条边 kk 交换后 AA 左块 A[0..k]A[0..k] 需恰好是 是否合法
0 (0,3,1,4,2)(0,3,1,4,2) {0}\{0\} {0}\{0\} ✅
1 (3,1,0,4,2)(3,1,0,4,2) {3,1}\{3,1\} {0,1}\{0,1\} ❌
2 (3,0,4,1,2)(3,0,4,1,2) {3,0,4}\{3,0,4\} {0,1,2}\{0,1,2\} ❌
3 (3,0,1,2,4)(3,0,1,2,4) {3,0,1,2}\{3,0,1,2\} {0,1,2,3}\{0,1,2,3\} ✅

两支合法分支:

  • k=0k=0:左子问题 [0,0][0,0] 的左端点值是 A[1]=0A[1]=0,得 f(0,0,0)=1f(0,0,0)=1; 右子问题 [1,4][1,4] 内容为 (3,1,4,2)(3,1,4,2)(内部位置 2,32,3 的值 1,41,4 来自 pp, 右端点补上没出现过的 22),得 f(1,4,3)=2f(1,4,3)=2。系数 (30)=1\binom{3}{0}=1,贡献 22。
  • k=3k=3:左子问题 [0,3][0,3] 内容 (3,0,1,2)(3,0,1,2) 得 f(0,3,3)=1f(0,3,3)=1;右子问题 [4,4][4,4] 得 11。 系数 (33)=1\binom{3}{3}=1,贡献 11。

合计 2+1=32+1=3,与暴力枚举出的 (2,1,0,3), (2,1,3,0), (2,3,1,0)(2,1,0,3),\ (2,1,3,0),\ (2,3,1,0) 这三个 qq 一致。

边界与坑。

  1. 下标与值的区分:要查的是"值 LL 在 pp 里的落点",与 p[L]p[L] 的值无关; 本解直接在区间内容数组上操作,不涉及这个混淆。
  2. 不可达子问题要剪掉:若区间内容不是 {L..R}\{L..R\} 的一个排列(有值越界或重复), 或某条边交换后左块值域对不齐,方案数记 00,不能进去递归。
  3. 组合数与累加全程取模:(R−L−1k−L)\dbinom{R-L-1}{k-L} 与两个子问题方案数都要先模后乘, 中间量用 64 位整数。
  4. 递归里的临时数组必须放局部:本解在每层递归内构造区间内容数组, 若写成全局数组会被更深的递归调用改坏。

代码

Python 版:

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

import sys
from functools import cache
from math import comb

MOD = 10 ** 9 + 7  # 答案取模的模数


@cache
def count(l: int, r: int, head: int, target: tuple[int, ...]) -> int:
    """区间 [l, r] 内的边各用一次、把恒等排列 [l..r] 变成目标排列的方案数。

    q 是 {0..n-2} 的全排列,每条相邻边恰好被用一次,任何数只能单向平移。
    倒过来看区间内最后一条被使用的边 k(交换位置 k, k+1):交换后左块 [l..k] 的数
    再也去不了右块,所以交换前必须已把 {l..k} 凑在左侧;余下 r-l-1 条边里左块占
    k-l 条、右块占 r-k-1 条,两段可任意交错,系数 C(r-l-1, k-l),两侧独立递归。
    head 是本区间最左位置上的值;合法子问题的内部位置 j 上的值恒等于 target[j],
    右端点上的值就是区间内没出现过的那个数。
    """
    if l == r:
        return 1 if head == l else 0        # 区间只剩一个位置,内容必须正好是它自己
    if not l <= head <= r:
        return 0                            # 最左位置上的值不属于本区间,该子问题不可达
    used = 1 << head                        # 位掩码记录区间内已出现的值
    for j in range(l + 1, r):
        v = target[j]
        mismatch = not l <= v <= r or used >> v & 1
        if mismatch:
            return 0                        # 区间内容不成形状,该子问题不可达
        used |= 1 << v
    rest = ((1 << (r - l + 1)) - 1) << l & ~used
    if rest == 0:
        return 0
    tail = rest.bit_length() - 1            # 右端点上的值 = 区间内剩下的那个数
    content = (head,) + target[l + 1:r] + (tail,)   # 下标 i-l 对应位置 i

    total = 0
    low, high = 1 << 60, -(1 << 60)         # content 前缀极值;前缀为空时两个约束自动成立
    for ko in range(r - l):                 # ko = k - l,最后一条边是 (k, k+1)
        k = l + ko
        in_left = low >= l and high <= k and l <= content[ko + 1] <= k
        if in_left:
            # 交换位置 k,k+1 后左侧恰好是 {l..k},两侧独立,再按 C(r-l-1, ko) 交错归并
            left_head = content[1] if ko == 0 else content[0]
            total += comb(r - l - 1, ko) * count(l, k, left_head, target) \
                * count(k + 1, r, content[ko], target)
        v = content[ko]
        low, high = min(low, v), max(high, v)
    return total % MOD


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                          # 排列长度
    p = tuple(next(data) for _ in range(n))  # 目标排列

    print(count(0, n - 1, p[0], p) % MOD)


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * 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-08 01:05
 * update_at: 2026-10-08 01:12
 */
// main.cpp:交换(一本通 1768)。反向区间 DP + 组合数归并。
//
// 题意:s 从恒等排列 [0..n-1] 出发,按 q_0, ..., q_{n-2} 的顺序做 n-1 次相邻交换
// (第 i 次交换 s[q_i] 与 s[q_i+1]),末态恰好是 p,求这样的排列 q 的个数。
// 因为 q 是 {0..n-2} 的全排列,每条相邻边 (i, i+1) 恰好被使用一次;
// 任何一个数跨过某条边就再也回不来,即任何数只能单向平移。
//
// 核心不变量:合法子问题的区间内容永远形如 [x, p[L+1], p[L+2], ..., p[R-1], y],
// 即内部位置 j 上的值恒等于 p[j],只有两个端点可能被祖先的交换"推"进来,
// 且区间内的值恰好构成 {L..R},x 一旦给定,y 就由"剩下的那个数"唯一确定。
// 于是区间状态只需 (L, R, 左端点上的值 head) 三项。
//
// 转移:倒着看区间 [L,R] 内最后一条被使用的边 k(交换位置 k, k+1)。
// 交换之后左块 [L,k] 里的数再也到不了右块,所以交换后左块的值域必须恰好是 {L..k}。
// 记交换前的区间内容为 c[L..R],则要求 c[L..k-1] 与 c[k+1] 全部落在 [L,k]
// (左边共 k-L+1 个数,全部落在 [L,k] 内即等价于正好填满),此时才存在这样的 k。
// 剩下的 R-L-1 条边中左子区间占 k-L 条、右子区间占 R-k-1 条,
// 两段互不干涉、可任意交错,归并系数为 C(R-L-1, k-L)。故
//     f(L, R, c) = Σ_{合法的 k} C(R-L-1, k-L) * f(L, k, A[L..k]) * f(k+1, R, A[k+1..R])
// 其中 A 是 c 交换位置 k,k+1 之后的区间内容。边界 f(L, L, c) = [c[L] == L],
// 答案即 f(0, n-1, p[0..n-1])。
//
// 复杂度:状态数 O(n^3),每个状态枚举 O(n) 条边、合法判断 O(1),合计 O(n^4)
// (n <= 50 时实测 8 ms,限时 1000 ms),空间 O(n^3)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll MOD = 1000000007LL; // 答案取模的模数
const int MAXN = 55;         // 题面 100% 数据 n <= 50,留一点余量
const int INF = 1 << 30;     // 前缀极值的哨兵初值

int n;                // 排列长度
int p[MAXN];          // 目标排列,p[i] 是下标 i 上的值
ll bino[MAXN][MAXN];  // bino[i][j] = C(i, j) 模 MOD
ll memo[MAXN][MAXN][MAXN]; // memo[L][R][head]
char done[MAXN][MAXN][MAXN]; // 该状态是否已算过,只存 0/1,用 char 省内存

// f(L, R, head):区间 [L,R] 内的边各用一次、把恒等排列 [L..R] 变成目标排列的方案数。
// head 是位置 L 上的值;右端点上的值由区间内容唯一确定,不必进状态。
ll solve(int L, int R, int head) {
    if (L == R) return head == L ? 1 : 0; // 区间只剩一个位置,内容必须正好是它自己
    if (head < L || head > R) return 0;   // 位置 L 上的值不属于本区间,该子问题不可达
    if (done[L][R][head]) return memo[L][R][head];
    done[L][R][head] = 1;

    int len = R - L; // 区间长度减一,也就是区间内的边数
    // 区间内容放局部数组:本函数会递归调用自己,全局数组会被递归改坏
    int ct[MAXN];    // ct[0..len] 对应位置 L..R
    ct[0] = head;
    for (int i = 1; i <= len - 1; i++) ct[i] = p[L + i]; // 内部位置保持原排列的值

    // 校验区间内容恰好是 {L..R} 的一个排列
    bool used[MAXN];
    for (int v = L; v <= R; v++) used[v] = false;
    used[head] = true;
    bool ok = true;
    for (int i = 1; i <= len - 1 && ok; i++) {
        int v = ct[i];
        if (v < L || v > R || used[v]) ok = false;
        else used[v] = true;
    }

    ll res = 0;
    if (ok) {
        int tail = -1; // 区间内没出现过的那个数,只可能是它站在右端点
        for (int v = L; v <= R; v++) {
            if (!used[v]) { tail = v; break; }
        }
        ct[len] = tail;

        int low = INF, high = -INF; // ct[0..ko-1] 的极值,前缀为空时约束自动成立
        for (int ko = 0; ko <= len - 1; ko++) {
            int k = L + ko; // 最后一条被使用的边是 (k, k+1)
            // 交换位置 k,k+1 后左侧是 ct[0..ko-1] 与 ct[ko+1],共 ko+1 个数,
            // 它们必须正好填满 [L,k];两边都落在 [L,k] 内即等价(个数已经吻合)
            bool good = low >= L && high <= k && ct[ko + 1] >= L && ct[ko + 1] <= k;
            if (good) {
                // 左子问题的左端点值:ko=0 时位置 k 换回来的是 ct[1],否则还是 ct[0]
                int leftHead = (ko == 0) ? ct[1] : ct[0];
                ll sub = solve(L, k, leftHead) * solve(k + 1, R, ct[ko]) % MOD;
                res = (res + sub * bino[len - 1][ko]) % MOD;
            }
            if (ct[ko] < low) low = ct[ko];
            if (ct[ko] > high) high = ct[ko];
        }
    }

    memo[L][R][head] = res;
    return res;
}

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

    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];

    // 组合数预处理(n <= 50,上界很小,直接 Pascal 三角形)
    for (int i = 0; i <= n; i++) {
        bino[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            bino[i][j] = (bino[i - 1][j - 1] + bino[i - 1][j]) % MOD;
        }
    }

    cout << solve(0, n - 1, p[0]) % MOD << "\n";

    return 0;
}

复杂度

  • 时间:状态是 (L,R,x)(L, R, x) 共 O(n3)O(n^3) 个;每个状态枚举 O(n)O(n) 条边, 判合法性用前缀极值 O(1)O(1) 完成(内部值的整体校验在进入状态时一次 O(n)O(n) 做完), 再乘两次子问题递归。故总复杂度 O(n4)O(n^4)。n≤50n \le 50 时 (50)4/24(50)^4/24 量级的实际调用 只有几百次,实测 main.cpp 在最坏的第 10 个测试点上 8 ms(限时 1000 ms)。
  • 空间:记忆化数组 O(n3)O(n^3) 个 long long,553×8≈1.355^3 \times 8 \approx 1.3 MB, 加递归栈 O(n)O(n),远低于 256 MB。
  • Python 侧:同一算法用 functools.cache + math.comb 实现,状态数完全相同, 第 10 个测试点实测 17 ms,不存在 TLE 风险。

总结

  • 时间轴上的"最后一步"是最强的结构:正向枚举 qq 是 (n−1)!(n-1)! 个纠缠的排列, 倒过来只看"某区间最后用哪条边",问题立刻裂成两个独立子问题。 这类"最后一步分治"是排列变换计数题的常用抓手。
  • 状态压缩靠不变量:区间内容 c[L..R]c[L..R] 的内部位置恒等于 pp 的对应值, 只有两个端点会被祖先推入,于是 O(n!)O(n!) 的内容被压成 O(n3)O(n^3) 的 (L,R,x)(L, R, x)。 写 DP 前先问一句"状态里有多少信息是冗余的"。
  • 组合数描述"互不干涉的两段如何交错":左块 k−Lk-L 条边与右块 R−k−1R-k-1 条边 内部次序已定,交错方案数就是 (R−L−1k−L)\binom{R-L-1}{k-L},这是分治 DP 的标准归并因子。
  • 数据说明:本题素材源里带 data.py 生成器,data/ 下 10 个测试点是自造的 (覆盖 n=1n=1 退化、n=2n=2 的两种情形、n=10n=10 恒等排列无解、由随机 qq 正向模拟出 的有解 pp、以及 n=50n=50 的结构极端与最大规模各一组),并非官方原始数据。 其中 n≤10n \le 10 的点已用 O((n−1)!⋅n)O((n-1)!\cdot n) 全排列暴力逐点复核过。