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

TimeTraveller · 2018-10-18 13:56:10 · 题解

先\rm Orz并感谢\rm Imagine的讲解。

之前的弱化版的我们直接用一个n^2的DP求取错排的方案数即可，但是这里不行。

我们先算出刚好K个配对的方案数量，然后乘以剩下的错排方案数，但是这个显然不是简单的错排了，因此不能直接套用公式。

前面的刚好K个配对的就是：

• 选k排座位C_n^k
• 选k对情侣C_n^k
• 这k对每排可以交换坐2^k
• 这k排可以任意排列k!

所以前半部分的答案就为(C_n^k)^2\times k!\times 2^k

那么对于错排部分，我们模仿错排递推的推导过程分类考虑，我们令g[n]为n对不匹配的方案数：

首先我们看第一排坐两个不是情侣的人，不难发现，那么可以有2n\times(2n-2)种选法，剩下只有n-1个座位，对于剩下的，我们考虑另外的两个（就是与开始那两个坐在一起的另一半情侣），他们有两种方案：

• 坐在一起：就是在剩下的n-1排中任选一排，且这个两个人可以交换，然后就转化为子问题g[n-2]，所以贡献为2\times (n-1)\times g[n-2]
• 不坐在一起，我们就把他们又看作一个不能在一起的错排问题，于是贡献为g[n-1]

和错排公式结合起来，所以这部分的方案数贡献为2n(2n-2)\left(g[n-1]+2(n-1)g[n-2]\right)

那么答案就是(C_n^k)^2\times k!\times 2^k\times 4n(n-1)\left(g[n-1]+2(n-1)g[n-2]\right)

预处理阶乘和阶乘逆元还有g函数和2的幂，然后每次O(1)的回答即可。

复杂度为O(logMod+n+T)

其中的logMod为处理一个阶乘的逆元。

代码太丑就不放上来了