容斥原理¶
集合的并¶
将三个集合内容相加，去重
{问题} 给定一个整数 \(n\) 和 \(m\) 个不同的质数 \(p_1, p_2, \ldots, p_m\)， 求 \(1 \sim n\) 中能被 \(p_1, p_2, \ldots, p_m\) 中的至少一个数整除的数有多少个？其中 \(m \leq 16, n, p_i \leq 10^9\)。
{例} \(n=10, p_1=2, p_2=3, p_3=5\)， 求 \(1 \sim 10\) 中能整除 \(2\) 或 \(3\) 或 \(5\) 的数的个数。 即 {2, 3, 4, 5, 6, 8, 9, 10}，共 8 个。 \(S_1=\{2, 4, 6, 8, 10\}\), \(S_2=\{3, 6, 9\}\), \(S_3=\{5, 10\}\)， \(S_1 \cap S_2=\{6\}\), \(S_1 \cap S_3=\{10\}\), \(S_2 \cap S_3=S_1 \cap S_2 \cap S_3=\{\}\)
{注意1}
- 交集的大小等于 \(n\) 除以质数的乘积。 即 \(|S_1|=\frac{n}{p_1}\), \(|S_1 \cap S_2|=\frac{n}{p_1 p_2}\), \(|S_1 \cap S_2 \cap S_3|=\frac{n}{p_1 p_2 p_3}\)
我们可以注意到以上特点，而不需要使用试除法
{注意2} 2. 使用二进制位来表示每个集合选与不选的状态。 若有 3 个质数，就需要 3 个二进制位来表示所有状态。 001 → \(S_1\), 010 → \(S_2\), 100 → \(S_3\), 011 → \(S_1 \cap S_2\), 101 → \(S_1 \cap S_3\), 011 → \(S_2 \cap S_3\), 111 → $S_1 \cap S_2 \cap S_3 $我们只要枚举从 001 到 111 的每个状态就可以计算出全部交集的交错和
代码
typedef long long LL;
const int N = 20;
int n, m, prim[N];
int calc() { //容斥原理
int res = 0;
for(int i=1; i<=m;i++) { //枚举状态
int t = 1, sign = -1;
for(int j=0;j<m;j++)//过滤状态
if(i & 1<<j){
if((LL)t*prim[j] > n){
t = 0; break;
}
t *= prim[j];
sign = -sign;
}
if(t)res +=n/t*sign;//交集的和
}
return res;
}
重点
重点理解
-
sign的含义 -
if((LL)t*prim[j]>n)的含义 -
位运算
复杂度 $ O(m\times 2^m)$
集合的交¶
e.g.
交集为{2,5}
注：绿框不是集合
例题
https://luogu.com.cn/problem/P1450
二项式反演¶
例题 #1 已经没有什么好害怕的了¶
题目描述
Charlotte 的结界中有两种具有能量的元素，一种是“糖果”，另一种是“药片”，各有 \(n\) 个。在 Charlotte 发动进攻前，“糖果”和“药片”会两两配对，若恰好糖果比药片能量大的组数比“药片”比“糖果”能量大的组数多 \(k\) 组，则在这种局面下，Charlotte 的攻击会丟失，从而 Mami 仍有消灭 Charlotte 的可能。
你必须根据 Homura 告诉你的“糖果”和“药片”的能量的信息迅速告诉 Homura 这种情况的个数.
输入格式
第一行两个整数 \(n,k\)，含义如题目所描述。
接下来一行 \(n\) 个整数，第 \(i\) 个数表示第 \(i\) 个糖果的能量。
接下来 \(n\) 个整数，第 \(j\) 个数表示第 \(j\) 个药片的能量。
保证上面两行不会有重复的数字。
输出格式
一个答案，表示消灭 Charlotte 的情况个数，需要对 \(10^9+9\) 取模。
【数据范围】 对于 \(100\%\) 的数据，\(1 \le n \le 2000\)，\(0 \le k \le n\)。
首先我们想把a,b排序，然后考虑匹配第i个a。将K=(n+k)/2，即我们恰好要K对a>b
如果用比a_i小的b取匹配它，那么后面的a的匹配方案就少了1.所以任意列出转移：
\(f_{i,j}=f_{i-1,j}+(r_i-(j-i))\times f_{i-1,j-1}\)。其中r_i表示b中比a_i 小的数字的个数。
此时的答案并不是\(f_{n,K}\)，因为我们还有n-K个a的匹配状态未知。我们让这些a随机匹配，记\(g_i=(n-K)!\times f_{n,i}\)，得到至少i对匹配的有重答案为\(g_i\)。
为上面说是“有重答案”呢？因为\(g_i\)中很明显是由一些重复方案的。
举个例子，\(f_{n,3}\)中包含了配对123，124，\(g_3\)中就可能包含123+4,124+3，这样就有重复了。那么这个重复的次数是多少呢？发现就是C(4,3)。
那么这里很显然要容斥了，可是怎么样容斥呢？设最终有恰好i对的答案为ans_i，那么我们就要找到ans_i和g_i之间的关系。
对于一个\(g_j,j≤i\)，我们发现\(g_j=\sum_{i=j}^n C(i,j)ans_i\)。这里我们就需要使用二项式反演了。
可以得到\(ans_j=\sum_{i=j}^nC(i,j) \times (-1)^{i-j}g_i\)
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif
const int N = 3e3 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 9;
int f[N][N];//考虑了前i个糖果的配对，其中糖果大的对数为j的方案数量
int fac[N],inv[N];
inline int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%MOD;
b>>=1;
a=a*a%MOD;
}
return res;
}
void init(){
fac[0]=1;
for(int i=1;i<N;i++){
fac[i]=fac[i-1]*i%MOD;
}
inv[N-1]=ksm(fac[N-1],MOD-2);
for(int i=N-1;i;i--){
inv[i-1]=inv[i]*i%MOD;
}
}
int a[N];
int b[N];
int r[N];
int g[N];
int ans[N];
int C(int n,int m){
if(n<m)return 0;
return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
void solve(){
int n=rd,K=rd;
// cdbg("OK");
init();
K=(n+K)>>1;
for(int i=1;i<=n;i++){
a[i]=rd;
}
for(int i=1;i<=n;i++){
b[i]=rd;
}
sort(a+1,a+n+1);
sort(b+1,b+n+1);
int j=0;
for(int i=1;i<=n;i++){
while(b[j+1]<a[i]&&j<n)j++;
r[i]=j;
// cdbg(a[i],r[i]);
}
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
f[i][j]=(f[i-1][j]+(j<=0?0:(r[i]-j+1)*f[i-1][j-1]%MOD)%MOD)%MOD;
}
}
for(int i=0;i<=n;i++){
g[i]=fac[n-i]*f[n][i]%MOD;
// cdbg(g[i],fac[n-i]);
}
for(int i=n;i>=K;i--){
int res=0;
for(int j=i+1;j<=n;j++){res+=C(j,i)*ans[j]%MOD;res%=MOD;}
ans[i]=((g[i]-res)%MOD+MOD)%MOD;
}
cout<<ans[K]<<endl;
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".in","w",stdout);
int T=1;
while(T--){
solve();
}
return 0;
}