题解

思路

关键结构

将所有区间按左端点递增排列。左端点不能相同；否则右端点较小的区间会被另一个包含。同理，右端点也两两不同，且必须与左端点保持相同的递增次序。

因此，只要选出两个大小为 $n$ 的坐标集合 $L,R$，并将第 $i$ 小的左端点与第 $i$ 小的右端点配对，就只需保证每个前缀中左端点数不少于右端点数。坐标 $x$ 必须选入 $L$。这样数出的是无标号区间集合，最后乘上 $n!$ 得到有序序列数。

做法

子任务 1：枚举区间序列

列出 $[1,m]$ 上的全部 $m(m+1)/2$ 个区间，枚举其中 $n$ 个不重复区间的排列。逐对判定包含关系，并检查是否有左端点 $x$。

设 $S=m(m+1)/2$，时间复杂度为 $O(P(S,n)n^2)$，空间复杂度为 $O(S+n)$。

子任务 2：位集合枚举端点

用两个 $m$ 位二进制集合分别表示 $L,R$。只枚举各有 $n$ 个位的集合，要求 $x\in L$，然后检查排序后每个 $l_i\le r_i$。每对合法端点集合贡献 $n!$。

时间复杂度上界为 $O(4^m m)$，空间复杂度为 $O(2^m)$。

子任务 3：端点扫描 DP

设 $f[a][b]$ 表示已处理若干个坐标，已放置 $a$ 个左端点、$b$ 个右端点的方案数。始终只保留 $0\le b\le a\le n$。对于当前坐标 $i$，有四种选择：

1. 不放端点；
2. 只放一个左端点；
3. 只放一个右端点；
4. 同时放一个左端点和一个右端点。

在 $i=x$ 时必须放左端点，所以只保留第 2、4 种转移。其他坐标保留全部四种转移。答案为 $f[n][n]\cdot n!$。

当 $n>m$ 时左端点无法两两不同，直接输出 $0$。否则由 $n\cdot m\le100000$ 和 $n\le m$ 可知 $n\le316$，因此 $O(mn^2)$ 复杂度可以通过。使用滚动数组后，空间复杂度为 $O(n^2)$。

独立组合数校验

设

$$B(p,a,b)=\binom pa\binom pb-\binom p{a+1}\binom p{b-1}.$$

根据反射原理，$B(p,a,b)$ 是在 $p$ 个坐标上选 $a$ 个左端点、$b$ 个右端点，且任意前缀中左端点不少于右端点的方案数。在 $x$ 之前枚举已放置的 $(a,b)$，再分别讨论 $x$ 处“只放左端点”和“左右都放”，可得到一个 $O(n^2)$ 的独立公式实现。本包用该实现与端点 DP 交叉验证。

复杂度

三层做法的时间复杂度依次为 $O(P(m(m+1)/2,n)n^2)$、$O(4^m m)$ 与 $O(mn^2)$；对应空间复杂度依次为 $O(m^2+n)$、$O(2^m)$ 与 $O(n^2)$。独立组合数校验为 $O(m+n^2)$ 时间、$O(m)$ 空间。

正确性证明

合法区间集合与满足前缀条件的端点选择一一对应：正向映射由排序后的端点得到；反向映射将第 $i$ 小的左、右端点配对，前缀条件保证 $l_i\le r_i$。递增次序保证任意两区间不互相包含。DP 精确枚举每个坐标对左、右端点的四种选择，并在 $x$ 禁止不含左端点的转移，因此 $f[n][n]$ 正好数出全部无标号合法集合。区间两两不同，乘 $n!$ 后正好得到所有有序序列。