受限排列：捆绑、插空与补集

间距约束的压缩换元

从 $1,\ldots,N$ 中选 $k\ge1$ 个整数 $a_1<\cdots<a_k$，要求相邻所选数的差至少为整数 $d\ge1$。令

原条件等价于 $1\le b_1<\cdots<b_k\le N-(k-1)(d-1)$；逆变换 $a_i=b_i+(i-1)(d-1)$ 恢复原选择。所以方法数为

前提是上标至少为 $k$，否则无解，计数为 $0$。$k=0$ 时空选择另计为 $1$。

例如从 $1,\ldots,20$ 中选 $5$ 个两两差至少为 $3$ 的数，共有 $\binom{12}5=792$ 种。这里排序只是给每个子集一个唯一表示，最终不用再乘 $5!$。

恰有一个孤立元素：改数连续段

对子集 $A\subseteq\{1,2,\ldots,n\}$，用长度 $n$ 的 $0,1$ 串表示选取情况。元素 $k$ 孤立表示它被选中、相邻整数均未选中；端点只检查存在的那个邻居。因此孤立元素恰对应长度为 $1$ 的连续 $1$ 段。

例如 $n=6$，要恰有一个孤立元素：

(1) 只有一段 $1$ 时，该段长度必须为 $1$，有 $6$ 种。

(2) 恰有两段时，一段长 $1$，另一段长 $k-1\ge2$，其中 $k$ 为选中的总数，所以 $k=3,4,5$。先选哪一段是单点段，有 $2$ 种。两段之间至少一个零，把这一零放好后，其余 $5-k$ 个零分配到前、中、后三处，有 $\binom{7-k}{2}$ 种。因此此类有

种。

(3) 三段或更多时，只有一段可长 $1$，另外两段至少各长 $2$，加段间至少两个零，长度至少 $1+2+2+2=7$，不能放入长度 $6$ 的串。

故共 $6+20=26$ 种。关键是数“长度为1的连续段”，不是只规定某点的两个邻居不选；后一做法还须排除别处出现第二个孤立点。

不允许同时选取的数：链与配对

倍数链。 从 $1,\ldots,N$ 选数，要求不能同时选 $x$ 和 $qx$，其中整数 $q\ge2$。将每个数反复除以 $q$，唯一归入一条 $b,bq,bq^2,\ldots$ 的链，其中 $b$ 不被 $q$ 整除。各链互不相交，限制只发生在相邻项之间。

长度 $L$ 的一条链，按相邻两项配对，至多选 $\lceil L/2\rceil$ 项；选第1、3、5…项可达。所以所有链分别选奇数位置就是全局最优。原题 $N=1995,q=15$，至多有三层：第1层有 $1995-133=1862$ 项，第3层有 $8$ 项，最优为 $1870$ 项。也可写成 $1995-\lfloor1995/15\rfloor+\lfloor1995/225\rfloor$。

按最大元素配对。 若 $B\subseteq\{1,\ldots,2n+1\}$ 不允许三个互异元素满足 $x+y=z$，取其最大元素 $m$。对 $1\le x<m$，把 $x$ 与 $m-x$ 配对，每对不同元素最多选一个；若 $m$ 偶数，单独的 $m/2$ 允许选，因为不能将它重复当成两个不同元素。

$m=2r+1$ 时，除 $m$ 外有 $r$ 对，故 $|B|\le r+1$；$m=2r$ 时有 $r-1$ 对及单个 $r$，加 $m$ 得 $|B|\le r+1$。两种均不超过 $n+1$。取 $\{n+1,\ldots,2n+1\}$ 可达，因两不同元素之和至少 $2n+3$。注意这里的“互异”正是中点可以保留的理由。

按余数分组处理成对禁选

从 $\{1,\ldots,50\}$ 选子集，要求任意两个不同元素之和不被 $7$ 整除。把数按除以 $7$ 的余数分为七组。

余数为 $0$ 的组最多选一个，因为两不同数之和仍被 $7$ 整除。余数对 $(1,6),(2,5),(3,4)$ 中，两组不能同时有选中的元素，否则任取一对就违例；每对最多保留较大的一组。同一非零余数组中的两数之和余数为 $2r$，不为 $0$，所以可以整组选取。

$1$ 至 $50$ 中，余数为 $1$ 的有八个，其余每组七个。因此最多 $1+8+7+7=23$ 个。选余数 $1,2,3$ 的全部数，再选一个 $7$ 的倍数，能达到此上界。

一般模数时先找哪些余数对相加为零；若模数为偶数，中间余数 $m/2$ 也像零余数一样最多选一个，不能照抄奇模数的分组结果。