题目大意

存在n对情侣，一共2 * n个人，现在要求每对情侣都不能相邻而坐，有多少种排序的方案。

Solution

首先这是一个环，所以1234与2341是同样的方案，那么从n对情侣中先把男生挑出来共n个人先去坐位子，共(n-1)!个方案。

接下来就是把剩下n个人插入进去了。
定义dp[i]代表安排完前i个人的时候的方案数。

1、dp[i-1] * (n+i-3)

上面的式子是直接插入方式，安排第i个人的时候，一共有n+i-1个人，那么就有n-i+1个位置可以选，但是又不能和自己情侣相邻，减掉她左右的两个位置即可。

2、dp[i-2] * (i-1) * 2

这个式子是间接插入，就是说现在在安排第i个人，但是第i-1个人我暂时安排他和他情侣在一起，把第i个人插入他们两者之间即可最后正常。

所以通过观察间接插入和直接插入是完全独立的两个方案，不会出现重复，注意特判一下n=1的情况即可。
所以最终答案就是 dp[i] = dp[i-1] * (n+i-3) + dp[i-2] * (i-1) * 2
最终把分配男生的(n-1)!的方案乘进去即可。

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 3e7 + 7;
const int MOD = 1e9 + 7;
ll a[N];

int main() {
    int n;
    scanf("%d", &n);
    if (n == 1)
        return puts("0"), 0;
    a[0] = 1, a[1] = n - 2;
    for (int i = 2; i <= n; ++i)
        a[i] = (a[i - 1] * (n + i - 3) % MOD + a[i - 2] * (i - 1) * 2 % MOD) % MOD;

    for (int i = 2; i < n; ++i)
        a[n] = a[n] * i % MOD;
    printf("%lld\n", a[n]);
    return 0;
}