首先因为是个环,我们得先随机分配一个确定起点,然后剩下的方案总数是(2*n-1)!.
然后就是我们的容斥原理了,0个相邻的-1个相邻的+2个相邻的-3+4...

0个相邻的答案就是(2*n-1)!
1个相邻的答案是2*C(n,1)*(2*n-2)!.

对于这个的解释就是你n对中选取1对,然后前后顺序考虑一下.
其他的同理,我们可以得到i对相邻的方案数是:

(2^i)*C(n,i)*(2*n-i)!.

如此这个题就可以通过预处理O(N)解决了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const ll N=3e7+5;
ll f[N],ivf[N];

ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void init()
{
    f[0]=1;
    for(ll i=1;i<=3e7;i++) f[i]=f[i-1]*i%mod;
    ll m=3e7;
    ivf[m]=qp(f[m],mod-2);
    for(ll i=m-1;i>=0;i--)
    {
        ivf[i]=ivf[i+1]*(i+1)%mod;
    }
}

ll C(ll n,ll m)
{
    return f[n]*ivf[m]%mod*ivf[n-m]%mod;
}

int main()
{
    ll n,ans=0;
    scanf("%lld",&n);
    init();
    ll p=1;//作为2的i次幂.
    for(ll i=0;i<=n;i++)
    {
        if(i&1) ans=(ans-p*C(n,i)%mod*f[2ll*n-i-1]%mod+mod)%mod;
        else    ans=(ans+p*C(n,i)%mod*f[2ll*n-i-1]%mod)%mod;
        p=p*2ll%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

mle..一般人会这么写吧...
换种写法...
这几次总是被int卡了...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=3e7+5;
int f[N],ivf[N];

int qp(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=1ll*res*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return res;
}

void init()
{
    f[0]=1;
    for(int i=1;i<=3e7;i++) f[i]=1ll*f[i-1]*i%mod;
    int m=3e7;
    ivf[m]=qp(f[m],mod-2);
    for(int i=m-1;i>=0;i--)
    {
        ivf[i]=1ll*ivf[i+1]*(i+1)%mod;
    }
}

int C(int n,int m)
{
    return 1ll*f[n]*1ll*ivf[m]%mod*ivf[n-m]%mod;
}

int main()
{
    int n,ans=0;
    scanf("%d",&n);
    if(n==0||n==1) {puts("0");return 0;}
    init();
    int p=1;//作为2的i次幂.
    ll cnm=f[n-1];
    p=qp(2,n);
    for(int i=n;i>=0;i--)
    {
        if(i&1) ans=(1ll*ans-1ll*p*C(n,i)%mod*1ll*cnm%mod+mod)%mod;
        else    ans=(1ll*ans+1ll*p*C(n,i)%mod*1ll*cnm%mod+mod)%mod;
        cnm=cnm*(2*n-i)%mod;
        p=1ll*p*ivf[2]%mod;
    }
    printf("%d\n",(ans%mod+mod%mod));
    return 0;
}

菜到自闭...优化个空间菜到自闭了