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

· · 题解

题目描述

有一个有 n 排但只有两列的电影院，同样有 n 对情侣，如果两个人坐在了一起，他们就是和睦的，问恰有 k 对情侣是和睦的方案数（注：男女交换后算另一种）

多组数据，对 998244353 取模。

1\leq T\leq 2\cdot 10^5\ ,\ 1\leq n\leq 5\cdot 10^6\ ,\ 0\leq k\leq n

solution

设一个函数 g(x) 表示 k=0 时的答案，于是答案就能表示成：

从 n 对情侣中选 k 对，从 n 排座位中选 k 排，一排上男女的两种坐法，k 对情侣怎么坐 k 排座位以及剩下的 n-k 对情侣的坐法，写出来，就是：

g_{n-k}\cdot {\left( \begin{array}{c} n \\ k\end{array} \right)}^2\cdot 2^k\cdot k!

所以现在就要推 g_n 。

如果先固定一排，那么两个人对应的伴侣就会有两种情况：

1.这俩伴侣看那两个人不爽，结果这俩又组一对，组了 n-1 次，然后两人交换一下位置，又有 n-1 种，最终剩下了 n-2 排。

2.随缘，直接就跟其他人跑了，就等于还剩 n-1 排。

所以就能表示成：

\big( 2\cdot (n-1)\cdot g_{n-2}+g_{n-1}\big)

最后就剩下这对我们强行配对的情侣了，他们的话，要么♂♂，要么♀♀，要么♂♀，总之都非常刺激的说，

易知♂♂或♀♀均为 \Large\frac{1}{2} \cdot n\cdot (n-1) ，♂♀为 n\cdot (n-1) ，并且交换一下位置又是一种，综上，就可以写成：

\big(\frac{1}{2}\cdot n\cdot (n-1)+\frac{1}{2}\cdot n\cdot(n-1)+n\cdot(n-1)\big)\cdot 2 \Rightarrow n\cdot (n-1)\cdot 4

带上去，就是

g_n=n\cdot (n-1)\cdot 4\cdot \big( 2\cdot (n-1)\cdot g_{n-2}+g_{n-1}\big)

预处理一下 g_n ，就能计算啦。

这题应该相对来说比较友好吧，就不放代码了。