思路详解：

方法一

考虑计数 dp。先将男生固定下来，由圆排列的方案数可知共 种方案。

接下来就是把剩下的 个人插入进去了。设 代表安排完前 个人的时候的方案数。转移如下：

  • ，这里的意思是直接插入，在第 个人进到队列之前，共有 个人已经在里面了，由于是一个圆，所以共有 个位置，考虑到不能和另外一个人站在一起，所以可选的位置有 个。直接使用乘法原理得到上面的转移方程。
  • ，这个式子是间接插入，就是说现在在安排第 个人，但是第 个人我暂时安排他和他情侣在一起，把第 个人插入他们两者之间即可最后正常。

最后的答案就是 。

方法二：

直接做其实并不好想，这种情况下我们优先考虑容斥。

令全集 ，集合 表示第 组违反规则的方案数。最后我们的答案是 ，直接套用容斥的公式即可。

事实上， 是可以直接算出来的，然后用一下圆排列方案数的那个结论，最后不难得到答案的公式：。

预处理阶乘和对应的逆元，带到答案那个式子算一下即可。

时间复杂度均为 。另外，这道题卡空间，写第二种写法的时候一定要注意。