最后的晚餐（dinner）
鏈接：
https://www.nowcoder.com/acm/contest/219/B
來源：牛客網
題目描述
\(\tt{**YZ}\)（已被和諧）的食堂實在是太擠辣！所以\(\tt{Apojacsleam}\)現在想邀請他的一些好友去校外吃一頓飯，并在某酒店包下了一桌飯。
當\(\tt{Apojacsleam}\)和他的同學們來到酒店之后，他才發現了這些同學們其實是\(N\)對\(cp\)，由于要保護廣大單身狗的弱小心靈（\(FF\)！），所以他不想讓任意一對情侶相鄰。
說明：
- 酒店的桌子是恰好有\(2N\)個位置的圓桌。
- 客人恰好是\(N\)對\(cp\)，也就是說，圓桌上沒有空位。
- 桌子的每一個位置是一樣的，也就是說，如果兩種方案可以通過旋轉得到，那么這就可以視為相等的。
- 現在，你需要求出，將任意一對情侶不相鄰的方案數。
說明
對于\(20\%\)的數據，\(1\le N\le 5\)
對于\(30\%\)的數據，\(1\le N\le20\)
對于\(50\%\)的數據，\(1\le N\le100\)
對于\(70\%\)的數據，\(1\le N\le 200000\)
對于\(100\%\)的數據，\(1\le N\le 30000000\)
思路：容斥原理
\(f_i\)代表至少\(i\)對情侶坐相鄰的方案數。
首先考慮一個小問題，\(n\)個人圍成一個可以旋轉的環的方案數。
可以固定第一個人，方案數就是\((n-1)!\)
那么\(f_i=fac_{2n-i-1}\times 2^i \times \binom{n}{i}\)
分別代表，捆綁法以后的方案數，情侶內部的方案數和選擇情侶的可能性。
答案就是\(\sum_{i=0}^nf_i(-1)^i\)
常數寫的不好。。說起來標程寫的好厲害，我都沒看懂。。
Code:
#include <cstdio>
#define ll long long
const ll mod=1e9+7;
const ll Inv=500000004;
const int N=3e7+10;
ll quickpow(ll d,ll k)
{ll f=1;while(k){if(k&1) f=f*d%mod;d=d*d%mod;k>>=1;}return f;
}
ll fac,tfac=1,ans=0,inv[N],po=1;
int n;
int main()
{scanf("%d",&n);if(n==1) return puts("0"),0;for(ll i=1;i<=n;i++) tfac=tfac*i%mod,po=po*2%mod;fac=tfac*quickpow(n,mod-2)%mod;inv[n]=quickpow(tfac,mod-2);for(ll i=n-1;~i;i--) inv[i]=inv[i+1]*(i+1)%mod;for(ll i=n;~i;i--){(ans+=fac*inv[i]%mod*inv[n-i]%mod*po%mod*(i&1?-1:1))%=mod;fac=fac*(2*n-i)%mod;po=po*Inv%mod;}ans=(ans+mod)%mod;ans=ans*tfac%mod;printf("%lld\n",ans);return 0;
}2018.10.28
