分析

一眼的数学题。因为原问题并不好做，按照正难则反，我们先考虑容斥。定义 表示至少有 对情侣坐在了一起。那么 。 为容斥系数。考虑单独的 如何求解。那么我们发现这是在求一个圆排列，根据 元素构成的圆排列方式为 。所以 。 表示 个有标号的元素的圆排列方式。最后 。注意一下空间限制，对于 要预处理。时间复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
const int N = 30000010,P = 1e9 + 7;
int qpow(int a,int b) {
    int x = 1;
    for(;b;b>>=1,a = 1LL * a * a % P) {
        if(b & 1) x = 1LL * a * x % P;
    }
    return x;
}
int ans = 0,fac[N * 2],ifac[N];
int C(int n,int m) {return 1LL * fac[n] * 1LL * ifac[m] % P * ifac[n - m] % P;}
signed main() {
    LL n = read();
    if(n == 0 || n == 1) {printf("0\n");return 0;}
    fac[0] = 1;
    for(int i = 1;i <= n * 2;i++) {fac[i] = 1LL * fac[i-1] * i % P;}
    ifac[n] = qpow(fac[n],P - 2);
    for(int i = n - 1;i >= 0;i--) {ifac[i] = 1LL * ifac[i + 1] * (i + 1) % P;}
    for(int i = n,Pow = qpow(2,n),Fac = fac[n - 1]; i >= 0 ;  Pow = 1LL * Pow * ifac[2] % P,Fac = 1LL * Fac * (2 * n - i) % P,i--) {
        if(i&1) ans = ((1LL * ans - (1LL * C(n,i) * Pow % P * 1LL * Fac % P)) % P + P) % P;
        else    ans = ((1LL * ans + (1LL * C(n,i) * Pow % P * 1LL * Fac % P)) % P + P) % P;
        // cout << ans << endl;
        // cout << Fac << " " << Pow << endl;
    }
    printf("%d\n",(ans % P + P) % P);
    return 0;
}