最后的晚餐（dinner）

鏈接：

https://www.nowcoder.com/acm/contest/219/B

來(lái)源：牛客網(wǎng)

題目描述

\(\tt{**YZ}\)（已被和諧）的食堂實(shí)在是太擠辣！所以\(\tt{Apojacsleam}\)現(xiàn)在想邀請(qǐng)他的一些好友去校外吃一頓飯，并在某酒店包下了一桌飯。

當(dāng)\(\tt{Apojacsleam}\)和他的同學(xué)們來(lái)到酒店之后，他才發(fā)現(xiàn)了這些同學(xué)們其實(shí)是\(N\)對(duì)\(cp\)，由于要保護(hù)廣大單身狗的弱小心靈（\(FF\)！），所以他不想讓任意一對(duì)情侶相鄰。

說(shuō)明：

• 酒店的桌子是恰好有\(2N\)個(gè)位置的圓桌。
• 客人恰好是\(N\)對(duì)\(cp\)，也就是說(shuō)，圓桌上沒(méi)有空位。
• 桌子的每一個(gè)位置是一樣的，也就是說(shuō)，如果兩種方案可以通過(guò)旋轉(zhuǎn)得到，那么這就可以視為相等的。
• 現(xiàn)在，你需要求出，將任意一對(duì)情侶不相鄰的方案數(shù)。

說(shuō)明

對(duì)于\(20\%\)的數(shù)據(jù)，\(1\le N\le 5\)
對(duì)于\(30\%\)的數(shù)據(jù)，\(1\le N\le20\)
對(duì)于\(50\%\)的數(shù)據(jù)，\(1\le N\le100\)
對(duì)于\(70\%\)的數(shù)據(jù)，\(1\le N\le 200000\)
對(duì)于\(100\%\)的數(shù)據(jù)，\(1\le N\le 30000000\)

---

思路：容斥原理

\(f_i\)代表至少\(i\)對(duì)情侶坐相鄰的方案數(shù)。

首先考慮一個(gè)小問(wèn)題，\(n\)個(gè)人圍成一個(gè)可以旋轉(zhuǎn)的環(huán)的方案數(shù)。

可以固定第一個(gè)人，方案數(shù)就是\((n-1)!\)

那么\(f_i=fac_{2n-i-1}\times 2^i \times \binom{n}{i}\)

分別代表，捆綁法以后的方案數(shù)，情侶內(nèi)部的方案數(shù)和選擇情侶的可能性。

答案就是\(\sum_{i=0}^nf_i(-1)^i\)

常數(shù)寫(xiě)的不好。。說(shuō)起來(lái)標(biāo)程寫(xiě)的好厲害，我都沒(mé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

轉(zhuǎn)載于:https://www.cnblogs.com/butterflydew/p/9867900.html

總結(jié)

以上是生活随笔為你收集整理的nowcoder OI 周赛 最后的晚餐（dinner） 解题报告的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。