题解：P16661 [GKS 2018 #H] Let Me Count The Ways

· · 题解

【题目传送门】

题目思路

令 S_i 表示第 i 对新婚夫妇满足条件的方案集合，显然，答案就是要求：

\left|\bigcap_{i=1}^mS_i\right|

但是仔细想想就会发现正着去求比较麻烦，所以考虑倒着去求，用总方案数，减去不合法的方案数。

易得 \left|\overline{S_i}\right| 就是强制第 i 对夫妻相邻时的方案数，这时候可以使用捆绑法，把第 i 对夫妻当成一个人来计算。显然，此时的方案数就是 A_{2n-1}^{2n-1}\times2，这里乘上一个 2 是因为两位交换也是一种新的方案。

所有不合法的方案就是所有 \overline{S_i} 的交集，在不考虑合不合法的情况下一共有 A_{2n}^{2n} 种方案，显然最终答案就是：

A_{2n}^{2n}-\left|\bigcup_{i=1}^{m}\overline{S_i}\right|

这时候就可以使用容斥原理了！

但是，如果是真的枚举是否选择每对夫妻的话是一共 2^m 个可能，无法接受，所以得考虑优化。

再细思，发现我们并不在意每次枚举的夫妻谁是谁，只要加、减去对应的方案数，所以我们只用算出一种可能就行了。综上，我们只用枚举选择的夫妻个数 j，求出第 1,\cdots,j 个的不合法方案，在乘上 C_m^j（我们一共可能有那么多种选择 j 对夫妻的方案）：对于每个 j，我们需要加上的可能方案数为：

(-1)^j\times C_m^j\times A_{2n-j}^{2n-j}\times2^j

综合一下，最终我们所求的答案就是：

\boxed{A_{2n}^{2n}-\sum_{j=1}^m\left[(-1)^j\times C_m^j\times A_{2n-j}^{2n-j}\times2^j\right] }

对于实际实现的时候，我们可以 O(N) 预处理出对于每个 i 的 i! 和 i! 在模 10^9+7 意义下的逆元。因为 10^9+7 是个素数，使用费马小定理即可。

:::success[AC 代码]{open}

#include<bits/stdc++.h>
#define TESTING 0
#define ift if(TESTING)
#define ft first
#define sd second
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define int long long
using namespace std;
const int N=2e5+5,INF=0x3f3f3f3f,MOD=1e9+7;
int cases=1;
int n,m,inv[N],fac[N];
auto qpow=[](int a,int b)->int{
    int res=1;
    while(b){
        if(b&1)res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res%MOD;
};
auto pre()->void{
    fac[0]=1;
    inv[0]=1;
    for(int i=1;i<=2e5;i++){
        fac[i]=fac[i-1]*i%MOD;
        inv[i]=qpow(fac[i],MOD-2)%MOD;
    }
}
auto A(int n,int m)->int{
    return fac[n]*inv[n-m]%MOD;
}
auto C(int n,int m)->int{
    return A(n,m)*inv[m]%MOD;
}
auto init()->void{}
auto solution()->void{
    cin>>n>>m;
    int ans=fac[2*n];
    for(int i=1;i<=m;i++){
        ans=(ans+(i%2==0?1:MOD-1)*1LL*C(m,i)%MOD*qpow(2,i)%MOD*A(2*n-i,2*n-i)%MOD+MOD)%MOD;
    }
    cout<<"Case #"<<cases<<": "<<ans<<"\n";
}
auto main()->signed{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    pre();
    while(T--){
        init();
        solution();
        cases++;
    }
    return 0;
}

:::