组合数学(新)

容斥

二项式反演

我们令 $f(i)$ 表示至少 $i$ 个元素满足某个条件，其他元素随便的方案数。$g(i)$ 表示恰好 $i$ 个元素满足某个条件的方案数。一般 $f(i)$ 很好求出，但我们想求 $g(i)$，就可以使用二项式反演：

形式一：

$$f(n)=\sum_{i=0}^n C_n^i \space g(i)\Longleftrightarrow g(n)=\sum_{i=0}^n(-1)^{n-i}\space C_n^i\space f(i)$$

形式二：

$$f(n)=\sum_{i=n}^m C_i^n \space g(i)\Longleftrightarrow g(n)=\sum_{i=n}^m(-1)^{i-n}\space C_i^n\space f(i)$$

题目

P4071 [SDOI2016] 排列计数

https://www.luogu.com.cn/problem/P4071

题目描述

求有多少种 $1$ 到 $n$ 的排列 $a$，满足序列恰好有 $m$ 个位置 $i$，使得 $a_i = i$。

答案对 $10^9 + 7$ 取模。多组测试数据

数据范围

对于全部的测试点，保证 $1 \leq T \leq 5 \times 10^5$，$1 \leq n \leq 10^6$，$0 \leq m \leq 10^6$。

笔记

令 $f(x)$ 表示为有 $x$ 个位置满足 $a_i=i$，剩下的位置随便放，那么就有 $f(x)=C_n^x\space (n-x)!=\frac{n!}{x!}$

但是 $f(x)$ 表示的是至少有 $x$ 个位置满足要求，可能满足要求的位置不止 $x$ 个，我们要求的是恰好 $x$ 个位置，那么令恰好 $x$ 个位置满足要求的方案数为 $g(x)$，有

$$f(x)=\sum_{i=x}^n C_i^x \space g(i)$$

反演：

$$\begin{align} g(x)&=\sum_{i=x}^n(-1)^{i-x}\space C_i^x\space f(i) \\ &=\sum_{i=x}^n(-1)^{i-x}\space \frac{i!}{(i-x)!x!}\space \frac{n!}{i!} \\ &=\frac{n!}{x!}\sum_{i=0}^{n-x}\frac{(-1)^i}{i!} \end{align}$$

后面那个求和式可以提前预处理出来，于是我们就可以 $O(1)$ 回答每个询问

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
#define _ 1000006
typedef pair<int,int> pii;
int fac[_],inv[_],pre[_];
inline int qpow(int a,int p,int res=1){for(;p;a=a*a%mod,p>>=1) if(p&1) res=res*a%mod;return res;}
inline void init(){
    fac[0]=1;
    for(int i=1;i<=1000000;i++) fac[i]=fac[i-1]*i%mod;
    inv[1000000]=qpow(fac[1000000],mod-2);
    for(int i=1000000-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    pre[0]=1;
    for(int i=1;i<=1000000;i++) pre[i]=(pre[i-1]+(i%2==0?1:-1)*inv[i]+mod)%mod;
}
inline void subtask(){
    int n,m;cin>>n>>m;
    cout<<fac[n]*inv[m]%mod*pre[n-m]%mod<<endl;
}
signed main(){
    init();
    ios::sync_with_stdio(false);
    int t;cin>>t;
    while(t--) subtask();
    return 0;
}

P10596 BZOJ2839 集合计数

https://www.luogu.com.cn/problem/P10596

题目描述

一个有 $N$ 个元素的集合有 $2^N$ 个不同子集（包含空集），现在要在这 $2^N$ 个集合中取出若干集合（至少一个），使得它们的交集的元素个数为 $K$，求取法的方案数，答案模 $10^9+7$。

数据范围

对于 $100\%$ 的数据，$1\leq N\leq 1000000$，$0\leq K\leq N$。

笔记

设 $f(x)$ 表示交集元素数量至少为 $x$ 的方案数，那么有 $f(x)=C_n^x\space(2^{2^{n-x}}-1)$ （先选出这 $x$ 个数，然后剩下的 $n-x$ 个数构成 $2^{n-x}$ 个集合，这些集合随便选，但不能一个都不选）

设 $g(x)$ 表示交集元素数量恰好为 $x$ 的方案数，则有 $f(x)=\sum_{i=x}^n C_i^x\space g(i)$

反演，有 $g(x)=\sum_{i=x}^nC_i^x\space (-1)^{i-x}f(i)$

直接求即可，其中求 $f(x)$ 的时候需要用到扩展欧拉定理

已经没有什么好害怕的了

https://vjudge.net/problem/黑暗爆炸-3622

题目描述

给出长度为 $n$ 的数组 $a$ 和 $b$，这 $2n$ 个数字互不相同。现在让 $a$ 中的数字和 $b$ 中的数字两两配对，使得 $a$ 中大于 $b$ 中的对数比 $b$ 中大于 $a$ 中的对数恰好多 $k$ 个，求方案数

数据范围

$1\le n \le 2000$

笔记

显然可以转化为要求配对出恰好 $\frac{n+k}{2}$ 个 $a$ 比 $b$ 大的组，如果 $n$ 和 $k$ 不同奇偶则无解

首先对 $a$ 中的数字进行排序，然后求得一个数组 $c$，$c_i$ 表示 $b$ 中有多少个数字可以小于 $a_i$。我们发现，如果 $i<j$，那么比 $a_i$ 小的数字一定比 $a_j$ 小，或者说如果我们给 $a_i$ 配对某个数之后，再考虑可供与 $a_j$ 配对的数字个数时，可以用 $c_j$ 减去当前已知匹配出来的组数。

于是就有 $dp[i][j]$ 表示前 $i$ 个数字匹配出来了 $j$ 组，$dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(c_j-j+1)$

再深入考虑一下 $dp[i][j]$ 的含义，我们是钦定了 $j$ 组，对于其他位置，我们还没有考虑怎么分配

令 $f(x)=(n-x)!\times dp[n][x]$，也就是我们把其余 $n-x$ 个位置随便配对，这些位置既可能是 $a$ 比 $b$ 大，也可能是 $b$ 比 $a$ 大，于是 $f(x)$ 就变成了至少有 $x$ 组 $a$ 比 $b$ 大的方案数。但我们要求恰好 $x$ 组的方案数，于是走个二项式反演就齐活了

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ls(k) (k)<<1
#define rs(k) (k)<<1|1
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+9;
#define _ 2003
typedef pair<int,int> pii;
int a[_],b[_],c[_],dp[_][_],fac[_],inv[_],n,k;
inline int qpow(int a,int p,int res=1){for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod;return res;}
inline int con(int n,int m){return fac[n]*inv[m]%mod*inv[n-m]%mod;};
inline int f(int x){return fac[n-x]*dp[n][x]%mod;};
inline void subtask(){
    cin>>n>>k;
    if((n+k)%2) return cout<<0,void();
    fac[0]=1;for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
    inv[n]=qpow(fac[n],mod-2);for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(b[j]<a[i]) c[i]++;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        dp[i][0]=1;
        for(int j=1;j<=i;j++){
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*max(c[i]-j+1,(int)0)%mod)%mod;
        }
    }
    int ans=0,x=(n+k)/2;
    for(int i=x;i<=n;i++) ans+=con(i,x)*((i-x)%2==1?-1:1)*f(i)%mod,ans%=mod;
    cout<<(ans+mod)%mod;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin>>t;
    while(t--) subtask();
    return 0;
}