题解：P16661 [GKS 2018 #H] Let Me Count The Ways
Yang_Xi
·
·
题解
题目大意
## 题目分析
$m$ 对人不能相邻的条件不好计算，考虑反着算。
设全集为 $2n$ 个人的排列，$A_i$ 表示第 $i$ 对夫妻**不**相邻的排列，$B_i$ 表示第 $i$ 对夫妻**相邻**的排列（即 $\overline{A_i}$）。
用公式：
$$
\left|\bigcap_{i=1}^{m}A_i\right|=|U|-\left|\bigcup_{i=1}^{m}B_i\right|
$$
把交集运算转成并集运算，
再运用容斥原理：
$$
\left|\bigcup_{i=1}^{m}B_i\right|=\sum_{k=1}^{m}(-1)^{k+1}\sum_{1\le i_1<i_2<\cdots<i_k\le m}\left|\bigcap_{j=1}^{k}B_{i_j}\right|
$$
，就可以把计算不相邻转换为计算相邻。
于是我们就可以枚举指定相邻的夫妻是哪些对，$k$ 对夫妻相邻的方案就是 $2^k(2n-k)!$ 种。
:::info[补充]
使用捆绑法，把指定相邻的夫妻捆绑起来，视作一个人。
原本共有 $2n$ 个人，捆绑 $k$ 对，等效于 $2n-k$ 个人，方案就是 $(2n-k)!$ 种。
但还需考虑每对捆绑的夫妻的内部方案，共 $2^k$ 种方案。
所以总方案数就是 $2^k(2n-k)!$。
:::
但直接枚举具体是哪几对夫妻会超时。
对于任意指定的 $k$ 对夫妻，相邻方案数均为 $2^k(2n-k)!$，因此只需按 $k$ 分类统计，而无需枚举具体是哪几对夫妻。
所以我们可以枚举相邻的夫妻对数，选择 $k$ 对夫妻的方案数是 $\binom{m}{k}$。
最终问题就变为了求
$$
\sum_{k=0}^m(-1)^{k}\binom{m}{k}2^k(2n-k)!
$$
的值。
对于求组合数所用的阶乘和逆元，计算时用的 $2^k$，$\mathcal{O}(N)$ 预处理即可。
时间复杂度为 $\mathcal{O}(TN)$。
## 参考代码
码风不好勿喷。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int Mod=1e9+7,N=1e5;
int inv[N*2+5],fac[N*2+5],pw2[N];
int pw(int a,int b){//快速幂
int sum=1,f=a;
while(b){
if(b&1)sum=(sum*f)%Mod;
f=(f*f)%Mod;
b>>=1;
}
return sum;
}
int C(int n,int m){//组合数
if(m>n||m<0)return 0;
return fac[n]*inv[m]%Mod*inv[n-m]%Mod;
}
int T,n,m;
void sol(int cas){
cin>>n>>m;
int sum=fac[2*n];
for(int i=1;i<=m;i++){//枚举捆绑对数
if(i&1)sum=((sum-C(m,i)*pw2[i]%Mod*fac[2*n-i]%Mod)%Mod+Mod)%Mod;
else sum=(sum+C(m,i)*pw2[i]%Mod*fac[2*n-i]%Mod)%Mod;
}
cout<<"Case #"<<cas<<": "<<sum<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cout.tie(0),cin.tie(0);
//预处理阶乘、逆元和2的幂
pw2[0]=fac[0]=1;
for(int i=1;i<=N;i++)pw2[i]=(pw2[i-1]<<1)%Mod;
for(int i=1;i<=N*2;i++)fac[i]=fac[i-1]*i%Mod;
inv[N*2]=pw(fac[N*2],Mod-2);
for(int i=N*2-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%Mod;
cin>>T;
for(int i=1;i<=T;i++)sol(i);
return 0;
}
```