题解 P4931 【[MtOI2018]情侣？给我烧了！（加强版）】

### 题意 把 $n$ 对情侣安排在 $n$ 行 $2$ 列的座位中，要求恰好有 $k$ 对情侣坐在一排中，问有多少种排法。询问数 $T\le2\times 10^5$，$k\le n\le5\times10^6$。 ### 题解 先考虑选出并排列坐在一起的 $k$ 对情侣，方案数为 $\binom{n}{k}^2\times k!\times 2^k$，其中 $\binom{n}{k}^2$ 为选出 $k$ 对情侣并选出 $k$ 行椅子的方案数，$k!$ 为 $k$ 对情侣排列顺序的方案数，$2^k$ 为每行情侣排列的方案数。设 $f_i$ 为 $i$ 对情侣都不坐在一排里的方案数（不考虑顺序），则最终答案为 $f_i\times 2^{n-k}\times(n-k)!\times\binom{n}{k}^2\times k!\times 2^k$。 再考虑计算 $f_i$，在这 $i$ 对情侣中任选一对，设为 $(a,b)$。设 $a$ 与 $c$ 坐在一起，且 $c$ 的情侣为 $d$，则可分类讨论为两种情况： - 第一种是 $b$ 和 $d$ 坐在一起，则方案数为剩余 $i-2$ 对情侣不坐一起的情况数，即 $f_{i-2}$； - 第二种情况是 $b$ 和 $d$ 不坐一起，那么就可以把 $b$ 和 $d$ 也看作一对不能坐一起的情侣，情况数就是剩余 $i-2$ 对情侣和 $b$ 和 $d$ 这对“情侣“排列的方案数，即 $f_{i-1}$。 则 $f_i=2(n-1)\times(f_{i-1}+f_{i-2})$，其中 $2(n-1)$ 为选出 $c$ 的方案数。则可以用递推预处理出 $f$ 数组和组合数、2 的幂等，然后 $O(1)$ 处理询问即可。 ### 注意 $f(0)=1,f(1)=0$