从恒等排列出发按 q 的顺序做 n-1 次相邻交换,倒着钦定每个区间最后使用的边,左块值域必须对齐,两段操作可自由交错,答案由区间 DP 乘组合数归并系数得到。
OJ: roj
题目 ID: 1768
难度:提高+/省选-
标签:动态规划区间DP组合数学python
创建: 2026-10-08 01:05
更新: 2026-10-08 01:05
形式化题目
给定
每个数只允许朝一个方向平移——它一旦跨过边
,这条边就用掉了, 而边不可重复使用,它再也回不来。
样例
正解
思路
朴素做法。 枚举
突破口:倒着想。 正向是"按时间顺序放边",
在区间
内,最后一条被使用的边是哪一条?
设这条边是
交换边
的那一刻,左块 里的数再也不可能跑到右块去,反之亦然。
所以交换之前左块
子问题的内容长什么样? 直接把"区间内每个位置站着哪个数"作为状态是
即区间内部位置
转移。 设
即交换后左块
边界
验证样例
| 最后一条边 |
交换后 |
左块 |
需恰好是 | 是否合法 |
|---|---|---|---|---|
| 0 | ✅ | |||
| 1 | ❌ | |||
| 2 | ❌ | |||
| 3 | ✅ |
两支合法分支:
:左子问题 的左端点值是 ,得 ; 右子问题 内容为 (内部位置 的值 来自 , 右端点补上没出现过的 ),得 。系数 ,贡献 。 :左子问题 内容 得 ;右子问题 得 。 系数 ,贡献 。
合计
边界与坑。
- 下标与值的区分:要查的是"值
在 里的落点",与 的值无关; 本解直接在区间内容数组上操作,不涉及这个混淆。 - 不可达子问题要剪掉:若区间内容不是
的一个排列(有值越界或重复), 或某条边交换后左块值域对不齐,方案数记 ,不能进去递归。 - 组合数与累加全程取模:
与两个子问题方案数都要先模后乘, 中间量用 64 位整数。 - 递归里的临时数组必须放局部:本解在每层递归内构造区间内容数组, 若写成全局数组会被更深的递归调用改坏。
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:状态是
共 个;每个状态枚举 条边, 判合法性用前缀极值 完成(内部值的整体校验在进入状态时一次 做完), 再乘两次子问题递归。故总复杂度 。 时 量级的实际调用 只有几百次,实测 main.cpp在最坏的第 10 个测试点上 8 ms(限时 1000 ms)。 - 空间:记忆化数组
个 long long,MB, 加递归栈 ,远低于 256 MB。 - Python 侧:同一算法用
functools.cache+math.comb实现,状态数完全相同, 第 10 个测试点实测 17 ms,不存在 TLE 风险。
总结
- 时间轴上的"最后一步"是最强的结构:正向枚举
是 个纠缠的排列, 倒过来只看"某区间最后用哪条边",问题立刻裂成两个独立子问题。 这类"最后一步分治"是排列变换计数题的常用抓手。 - 状态压缩靠不变量:区间内容
的内部位置恒等于 的对应值, 只有两个端点会被祖先推入,于是 的内容被压成 的 。 写 DP 前先问一句"状态里有多少信息是冗余的"。 - 组合数描述"互不干涉的两段如何交错":左块
条边与右块 条边 内部次序已定,交错方案数就是 ,这是分治 DP 的标准归并因子。 - 数据说明:本题素材源里带
data.py生成器,data/下 10 个测试点是自造的 (覆盖退化、 的两种情形、 恒等排列无解、由随机 正向模拟出 的有解 、以及 的结构极端与最大规模各一组),并非官方原始数据。 其中 的点已用 全排列暴力逐点复核过。