一些错排问题

· · 算法·理论

基础错排问题

例题。

设 n 个信封的答案为 D_n。

目前已经求出了 D_{1\sim n-1} 的方案数，考虑 D_n 怎么求。

若将 n 号信放入 k 号信封，则 k 号信可以放入 n 号或其它信封。若放入 n 号信封，则对其余 (n-2) 封信没有影响，方案数为 D_{n-2}；否则相当于变为 k 号信对应 n 号信封，方案数为 D_{n-1}。

由于 n 号信可以放入 n-1 个信封，所以 D_n=(n-1)(D_{n-1}+D_{n-2})。

无限制元素

对于所有 1\sim n 的排列 p，求满足对于任意 1\le i\le m 有 p_i\not= n 的方案数。

显然在 m=n 时答案为 D_n。考虑有 0\le k\le n-m 个未受限的元素放在了原位，则其它元素方案为 D_{n-k}，于是总答案为

\sum_{i=0}^{n-m} C_{n-m}^i D_{n-i}

。

二重错排

对于所有 1\sim n 的排列 p，求满足对于任意 1\le i\le m 有 p_i\not= i 且 p_i\not=(i\bmod n)+1 的方案数。

把 p_i 拆成两个点 a_{2i},a_{2i+1}\in{0,1}，若 a_{2i}=1 则表示 p_i=i，若 a_{2i+1}=1 则表示要求 p_i=(i\bmod n)+1。故要求 k 个不满足条件相当于在 a_{1\sim 2n} 中选 k 个设为 n，且不存在 a_i=a_{(i\bmod 2n)+1}=1（若相邻项为 1 则代表了有一个 p_i 同时是两个数或有一个数同时在两个 p_i）。

先考虑在仅要求不存在 a_i=a_{i+1}=1(1\le i<2n) 时的做法。这就相当于在 2n-k 个零中插入 k 个一，插板法可得答案为 C_{2n-k+1}^k。接下来考虑原问题。若 a_1=0，则剩下的 2n-1 位就变成了上述简化问题，答案为 C_{2n-k}^k；若 a_1=1，则 a_2=a_{2n}=0，剩下的 2n-3 位就变成了上述简化问题，答案为 C_{2n-k-1}^{k-1}。所以这部分的答案为 C_{2n-k}^k+C_{2n-k-1}^{k-1}。

因此可以容斥计算，答案为

\sum_{k=0}^n (-1)^k(n-k)!(C_{2n-k}^k+C_{2n-k-1}^{k-1})

。

范围限制

对于所有 1\sim n 的排列 p，求满足对于任意 1\le i\le m 有 p_i>k 的方案数。

将其转化到棋盘上放置互不攻击的车。那么会发现限制相当于左上角 m\times k 的方形不能放置车。那不就是 P1350 吗？

练习题

P3182

容易发现其实就是最基础的错排问题。高精度即可。

P4071

显然钦定了 m 个位置之后就变成基础错排问题了，因此答案为 C_n^mD_{n-m}。

CF888D

枚举固定位置的点的个数即可。答案就是 \sum_{i=n-k}^n D_{n-i}C_n^i。

UVA 11481

前 m 个有 k 个在原位，则剩下的 n-k 个元素就是 m-k 个有限制元素和 n-m 个无限制元素，直接套上面的柿子可得答案为

C_m^k \sum_{i=0}^{n-m} C_{n-m}^i D_{n-k-i}

CF340E

设剩下 m 个需要填，有 k 个数满足未被确定且 a_k 被确定。那么这 k 个数就是没有限制的元素，剩下要填的 m-k 个元素有限制。于是用 无限制元素 一节的方法即可。

ABC172E

数列 a 显然有 A_m^n 种选法。接下来计算数列 b 的方案数。显然可以转化为填 1\sim m 中的 n 个且 b_i\not=i 的方案数 D'_n。考虑递推求出 D'。发现填到任意位时，总有 m-n 个无限制的元素（将一个无限制的元素填入后，原本应该在这一位填的数就变为了无限制元素）。所以在第 i 位填无限制元素的总方案数为 (n-m)D'_{i-1}。因此 D'_i=(n-m)D'_{i-1}+(n-1)(D'_{i-1}+D'_{i-2})。注意此时 D_1=n-m。

ABC214G

问题可以被转化为 r_i\not=i 且 r_i\not= p_i 的排列 r 的数量。连边 i\to p_i，则形成了若干个环。那么在一个大小为 s 的环内有 k 个不满足条件的点的方案数可以用 二重错排 一节中的方式计算，也即 C_{2s-k}^k+C_{2s-k-1}^{k-1}。然后可以合并到一整个序列中有 i 个不满足条件的点的方案数 f_i，于是该问题的答案为

\sum_{k=0}^n (-1)^k f_k(n-k)!

。

SP9097

设 s 为不同数的数量，f_{i,j} 为当前到第 i 种数，且有 j 个位置的 a_p=b_p 时的方案，cnt_i 为第 i 种数的数量。那么有

f_{i,j}=\sum_{k=0}^{\min(j,cnt_i)} f_{i-1,j-k}C_{cnt_i}^k\dfrac{((\sum_{t=1}^icnt_t)-j)!}{((\sum_{t=1}^{i-1}cnt_t)-j+k)!(cnt_i-k)!}

。其中 \sum_{k=0}^{\min(j,cnt_i)} 是在枚举当前颜色中 a_p=b_p 的个数 k，f_{i-1,j-k} 是从之前的状态转移过来，C_{cnt_i}^k 是在这 cnt_i 个中选 k 个的方案数，\frac{((\sum_{t=1}^icnt_t)-j)!}{((\sum_{t=1}^{i-1}cnt_t)-j+k)!(cnt_i-k)!} 是增加的这 cnt_i 个数使得剩余的 (\sum_{t=1}^i cnt_t)-j 个数增加的排列方案数。

对 cnt 做个前缀和即可做到 O(n\sum cnt)=O(n^2)。