最后的晚餐

一眼看上去就是一个经典题啊

直接考虑不是很容易那就容斥

全部方案为：
一对相邻：,此情况有种
两对相邻：,此情况有种
……
所以：

最后预处理一下就可以了。

#include<bits/stdc++.h>
#define ll long long
const ll N=30000010,INF=0x3f3f3f3f,P=1e9+7;
using namespace std;

inline ll read()
{
    register ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

ll ans=0,fac[N<<1],inv[N];

ll qpow(ll a,ll b) 
{
    ll x=1;
    for(;b;b>>=1,a=1LL*a*a%P) 
        if(b&1) x=1LL*a*x%P;
    return x;
}

ll find(ll n,ll m) 
{
    return 1LL*fac[n]*1LL*inv[m]%P*inv[n-m]%P;
}

int main() 
{    
    ll n=read();
    if(n==1) {printf("0");return 0;}
    fac[0]=1;
    for(ll i=1;i<=n*2;i++) fac[i]=1LL*fac[i-1]*i%P;
    inv[n]=qpow(fac[n],P-2);
    for(ll i=n-1;i>=0;i--) inv[i]=1LL*inv[i+1]*(i+1)%P;
    ll Pow=qpow(2,n),Fac=fac[n-1];
    for(ll i=n;i>=0;i--) 
    {
        if(i&1) ans=((1LL*ans-(1LL*find(n,i)*Pow%P*1LL*Fac%P))%P+P)%P;
        else    ans=((1LL*ans+(1LL*find(n,i)*Pow%P*1LL*Fac%P))%P+P)%P;
        Pow=1LL*Pow*inv[2]%P,Fac=1LL*Fac*(2*n-i)%P;
    }
    ans=(ans%P+P)%P;
    printf("%lld",ans);
    return 0;
}