P4921 [MtOI2018] 情侣关系，为何要被烧毁呢？

P4921 [MtOI2018] 情侣？给我烧了！ 大意 \(n\) 对情侣，恰好 \(k\) 对在 \(2 \times n\) 的电影院中坐一起的方案数。 思路 很好的题目，使得我的大脑旋转。 首先我们先定义函数 \(f(n, k)\) 表示 \(n\) 对情侣有 \(k\) 对恰好坐到一块的方案数。首先我们要从 \(n\) 对情侣中选择 \(k\) 对，这个是 \(\binom{n}{k}\) 的，再从 \(n\) 排选择 \(k\) 排，这个也是 \(\binom{n}{k}\) 的，考虑到这 \(k\) 对情侣间也有先后顺序，贡献就是 \(k!\)，两人可以换位，贡献是 \(2 ^ k\)，剩下有 \(n - k\) 对情侣，我们只需要将其错排即可。 定义 \(g(m)\) 表示 \(m\) 对情侣错排的方案数，我们考虑这个怎么求。这个我们可以利用容斥原理，我们考虑直接计算至少 \(j\) 对和睦的方案数，那么这个的贡献与上面的类似，应当是 \(\binom{m}{j} ^ 2 j! 2 ^ j (2(m - j))!\)，那么由容斥可知： \[g(m) = \sum_{j = 0} ^ {m}(-1) ^ j \binom{m}{j} ^ 2 j! 2 ^ j (2(m - j))! \] 那么我们合并一下整个式子，就是： \[f(n, k) = \binom{n}{k} ^ 2 k ! 2 ^ k g(n - k) \\ = \binom{n}{k} ^ 2 k ! 2 ^ k \sum_{j = 0} ^ {n - k}(-1) ^ j \binom{n - k}{j} ^ 2 j! 2 ^ j (2(n - k - j))! \] 这个式子我们是可以直接求的，于是就完成了。