容斥定理整理

amiracle2025-09-222025-09-28

前置知识-容斥定理:

将事件 A，表示成多个子事件 A₁, A₂...A_k 的并集，不要求事件互斥，即 ⋃Ai = A

容斥定理，可以让我们用这些子事件的交集计算整个事件

1. 两集合的简单容斥

2. 更一般的容斥定理

3. 子集容斥-子集反演

$为某集合，若两个函数满足如下关系：则其逆运算为：$

洛谷P10580

题意

长度为 n 的序列 a, gcd (a) = x, lcm(a) = y, 求序列方案数

解析

对于x，y，由唯一分解定理，我们可拆解成如下形式

不同质因子相互独立，考虑研究某个质因子，假设是 p₁

分解 a_i = p₁^k_i1p₂^k_i2p₃^k_i3...

因为gcd (a) = x，我们有 min k_i1 = c₁

因为lcm(a) = x，我们有 max k_i1 = e₁

也就是所有序列中所有数，都要满足， $质因子的幂$ ，且至少存在一个数的幂是 c₁，至少存在一个数的幂是 c₂

设 t = y/x，分解 t = p₁^k₁p₂^k₂p₃^k₃...

对于某种质因子，我们等价转化成如下问题：

有 n 个盒子，每个盒子可以放 [0, k] 个球，至少有一个盒子放了 0 个，且至少有一个盒子放了 k 个，求方案数

正向算不好算，考虑无 0，无 k

$定义：没有盒子放了个的情况集合，没有盒子放了个的情况集合$

$定义：至少有一个盒子放了个，且至少有一个盒子放了个的情况集合$

易得，A = U − A₁ ∪ A₂

由容斥定理

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mo = 998244353;

ll qpow(ll a, ll x){
    ll ans = 1;
    while(x){
        if(x & 1) ans *= a;
        a *= a;
        x >>= 1;

        a %= mo;
        ans %= mo;
    }
    return ans;
}

int main(){
    int q;
    cin >> q;
    for(int qq=0; qq<q; qq++){
        int x, y, n;
        cin >> x >> y >> n;
        int z = y/x;

        // 分解质因子
        map<int, int> fct;
        for(int i=2; i*i<=z; i++){
            while(z % i == 0){
                z /= i;
                fct[i]++;
            }
        }
        if(z != 1) fct[z]++;

        ll ans = 1;
        for(auto [p, k] : fct){ // 计算每种质因子的答案 , 每种质因子情况独立
            ans *= (qpow(k+1, n) - 2*qpow(k, n) + qpow(k-1, n)) % mo;
            ans = (ans%mo + mo) % mo;
        }
        cout << ans << '\n';
    }
}

ZJU-Summer 2023

题意

n ⋅ m 个格子, 每个格子都可以放或不放宝石，且每行每列都至少有一个宝石，求方案数

(n, m ≤ 5e4)

解析

正向算不好算，考虑存在空行或空列，设为情况集合 S，ans = 2^nm − |S|

容斥定义 :

定义：r_i 为第 i 行为空的情况集合，c_i 为第 i 列为空的情况集合

定义：R_i 为至少有 i 行为空的情况集合，C_i 为至少有 i 列为空的情况集合

$或$

发现 i，j 可以分开，简化求和。

由于没有 i + j = 0 这一项，即没有 i = j = 0 的情况，这种情况我们要减去

$易得，代入$

O(n²)复杂度，还需要继续优化，可将 i 提出

回忆一下二项式定理 →

你可能已经注意到了，不正是二项式定理的形式么

我们让它更规范一些 →

所以我们有

终于，到现在 |S| 就可以 o(nlog) 计算了

递推预处理一下，这样，这道题就完美解决了

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int mo = 1e9 + 7;
 
const int MX = 2e5;
vector<ll> fct(MX+1);
vector<ll> inv_fct(MX+1);
vector<ll> inv(MX+1);
 
void init(){ // 预处理
    fct[0] = inv_fct[0] = inv[1] = 1;
    for(int i=2; i<=MX; i++){
        inv[i] = (mo - mo / i) * inv[mo % i] % mo;
    }
    for(int i=1; i<=MX; i++){
        fct[i] = fct[i-1] * i % mo;
        inv_fct[i] =inv_fct[i-1] * inv[i] % mo; 
    }
}
 
ll comb(ll n, ll k){ // C(n, k) 组合数
    ll ans = 1ll * fct[n] * inv_fct[n-k] % mo * inv_fct[k] % mo;
    return ans;
}
 
ll qpow(ll a, ll x){ // 快速幂
    ll ans = 1;
    while(x){
        if(x & 1) ans *= a;
        a *= a;
        x >>= 1;
        
        a %= mo;
        ans %= mo;
    }
    return ans;
}
 
void solve(){
    int n, m;
    cin >> n >> m;
    ll ans = 0;
    for(int i=0; i<=n; i++){
        ans += (i&1? -1:1) * comb(n, i) * qpow((qpow(2, n-i) - 1), m) % mo;
        ans = (ans + mo) % mo;
    }
    cout << ans << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();

    int t = 1; cin >> t;
    while(t--) solve();

    return 0;
}

ABC423-F

题意

y ∈ [1, Y]，有 n 种事件A₁…A_n，每种事件仅在 a_i ∣ y 时发生，求有多少个 y，能使恰好 m 个事件发生

( m ≤ n ≤ 20, Y ≤ 1e18, a_i ≤ 1e18 )

解析

子集容斥(子集莫比乌斯反演)：

事件集合 S

设 g(S) 为至少覆盖 S 的情况数 (S中的事件全发生，其他事件可以发生或不发生)

设 f(S) 为恰好 S 的情况数 (仅S中事件发生，其他事件不发生)

$显然，为中所有事件的的$

我们有 g(S) = ∑_{S ⊆ T ⊆ U} f(T)

由子集反演公式：

我们需要计算满足|S|=m 的所有子集 S 的答案，即

又到了精彩的推式子环节

对于每个子集去枚举超集，时间复杂度 o(3ⁿ)，需要优化

可以交换 S, T 求和顺序

这样就优化完了

枚举 m ≤ |T| 的所有子集，O(2ⁿ)

预处理 g(T)，O(2ⁿlog)

$预处理，$

总时间复杂度 O(2ⁿlog + n)

MYCODE

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128 = __int128;

const ll inf = 2e18;

// fct[20] 刚好不会爆 ll 
// MX 再大些可以用 n^2 递推求
const int MX = 20;
vector<ll> fct(MX + 1);
void init(){ 
    fct[0] = 1;
    for(int i=1; i<=MX; i++){
        fct[i] = i * fct[i-1];
    }
}

void solve(){
    ll n, m, Y;
    cin >> n >> m >> Y;
    vector<ll> a(n);
    for(int i=0; i<n; i++) cin >> a[i];

    // 得到最低位 1
    auto get = [&](ll x){
        int p = __lg(x & -x);
        return p;
    };
    
    auto comb = [&](ll n, ll k){
        return fct[n] / fct[n-m] / fct[m];
    };

    vector<ll> pre(1 << n, 1), g(1 << n); // 预处理 lcm(S), g(S)
    int full = (1 << n) - 1;
    for(int S = 1; S <= full; S++){
        int lo = get(S);
        i128 l = i128(pre[S ^ (1 << lo)]) * a[lo] / gcd(pre[S ^ (1 << lo)], a[lo]);

        if(l > Y){ // g(S) = 0;
            pre[S] = inf;
            continue;
        }

        pre[S] = l;
        g[S] = Y / pre[S];
    }

    // ull 技巧，因为答案不会爆 ll，但过程计算可能爆，可以直接用 ull，自带取模
    ull ans = 0;
    for(int S = 1; S <= full; S++){
        int k = __builtin_popcount(S);
        if(k < m) continue;
        ans += 1ull * comb(k, m) * g[S] * ((k-m)&1? -1:1);
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();

    int t = 1; //cin >> t;
    while(t--) solve();

    return 0;
}