最后的晚餐(dinner)

不得不说是个垃圾题目,这样可以卡空间真的没必要.....

圆排列个数是,因为可以以任意一个点开头

那么考虑至少有一对情侣相邻,也就是,选一对情侣出来

现在把这对情侣看成一个整体,就只剩下个人排列了

情侣内部可以正反,再乘以

接下来就上容斥把

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e7+10;
const int mod=1e9+7;
ll quick_pow(ll x,ll n)
{
    ll ans=1;
    while( n )
    {
        if( n&1 )    ans = ans*x%mod;
        x = x*x%mod; n>>=1;
    }
    return ans;
}
int fac[maxn],n,inv[maxn];
int C(int n,int m)
{
    return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main()
{
    cin >> n;
    if(n==1) {printf("0");return 0;}
    fac[0]=1;
    for(int i=1;i<=n*2;i++)
        fac[i] = (ll) fac[i-1] * i % mod;
    inv[n] = quick_pow( (ll)fac[n],(ll)mod-2 );
    for(int i=n-1;i>=0;i--)
    {
        inv[i] = (ll)inv[i+1]*(i+1)%mod;
    }
    ll er=quick_pow(2,n),ans=0,FAC=fac[n-1];
    for(int i=n;i>=0;i--)
    {
        ll temp = (ll)C(n,i)*er%mod*FAC%mod;
        er = (ll)er*inv[2]%mod;  FAC = FAC*(2*n-i)%mod;
        if( i&1 )    ans = (ans-temp)%mod;
        else    ans = (ans+temp)%mod;
        ans = (ans+mod)%mod;
    }
    printf("%lld", (ans%mod+mod)%mod );
}