数组合数学

容斥计数

字数统计: 1.3k字   |   阅读时长: 5分
,

摘要: 容斥计数的例题，可以作为代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

对于一些计数或者概率类型的动态规划问题，有时候答案是要求恰好满足某条件时的答案，但是难以限制成恰好的情况，可以考虑试图放宽条件，改成类似于至少达到某条件的状态。这个时候可以先构造出满足各种至少的情况。最后统计答案的时候用容斥。

在文章 组合数学4-容斥原理,鸽巢原理 中，我们介绍了容斥原理，当集合个数为 2 个，3 个，N 个时，例题如下：

  • (1) 两个集合的容斥：力扣 920
  • (2) 3 个集合的容斥：力扣 1201
  • (3) N 个集合的容斥：acwing 216

集合个数变多后，容斥原理的实现难度会变大，本文我们通过 (3) 看一下集合个数比较多的时候，如何实现通过容斥原理进行计数，并形成代码模板。

两个集合的容斥

题解参考：【DP难题】力扣920-播放列表数量

三个集合的容斥

题解参考：最大公约数算法以及C++17组件

N 个集合的容斥

N 个盒子，第 i 个盒子有 $A_{i}$ 枝花，同一盒子内花颜色相同，不同盒子内的花颜色不同。

从这些盒子中选出 M 枝花形成一束。若两束花每种颜色的数量都相同，视为相同方案。求方案数。模 1e9 + 7 后输出。

1
2
3
4
5
6
7
8
9
10
11
12
输入格式
第一行包含两个整数 N 和 M 。

第二行包含 N 个空格隔开的整数，表示 A1,A2,…,AN。

输出格式
输出一个整数，表示方案数量对 1e9+7 取模后的结果。

数据范围
1<=N<=20,
0<=M<=1e14,
0<=Ai<=1e12

输入样例：
3 5
1 3 2
输出样例：
3

算法：容斥原理

第 i 盒子的颜色为 $B_{i}$，从多重集合 $\{A_{i} * B_{i}\}, i=1,2,…,N$ 中，选出 M 个元素能够形成的不同多重集数量。

结果公式如下：

下面看一下如何计算上面的公式。

枚举 $x \in [0, 2^{N}-1]$，若 x 在二进制下共有 p 位为 1，分别是第 $i_{1}, i_{2}, …, i_{p}$ 位，则这个 x 就代表上式中的一项：

特别地，x = 0 代表 $\dbinom{N+M-1}{N-1}$，这样就可以计算多重集组合数公式的每一项。对于每一项，要求一个组合数。

得到以上结果公式的分析和推导过程，以及计算以上公式的代码模板，参考文章 多重集的组合数。

代码 (C++)

下面的 multiple_combination 是给定多重集合 $\{n_{i} * a_{i}\}, i=1,2,…,k$，其中元素 $a_{i}$ 有 $n_{i}$ 个，从中选出 m 个元素能够形成的不同多重集数量的代码模板。

多个集合的容斥原理的实现过程类似，可以参考这个代码模板。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

const int MOD = 1e9 + 7;
using ll = long long;

// 快速幂求逆元

int quickpower2(int a, int n, int m) // 处理不了n是负数
{
    int ans = 1;
    while(n)
    {
        if(n & 1) ans = ((ll)ans * a) % m;
        a = (ll)a * a % m;
        n >>= 1;
    }
    return ans;
}

ll get_inv(ll b, ll p)
{
    return quickpower2(b, p - 2, p);
}

// 预处理逆元

vector<int> inv;

void init(int N)
{
    inv.assign(N, -1);
    for(int i = 1; i < N; ++i)
        inv[i] = get_inv(i, MOD);
}

int C(ll n, int m, int MOD)
{
    // n < 0 和 n < m 的情况在调用方处理
    n %= MOD;
    int ans = 1;
    for(int i = 0; i < m; ++i)
        ans = (ll)ans * (n - i) % MOD;
    for(int i = 1; i <= m; ++i)
        ans = (ll)ans * inv[i] % MOD;
    return ans;
}

int multiple_combination(const vector<ll>& n, ll m, int MOD)
{
    int ans = 0;
    int k = n.size();
    for(int x = 0; x <= pow(2, k) - 1; ++x)
    {
        // 枚举 x 中所有为 1 的位
        ll t = k + m;
        int p = 0; // x 中有 p 个 1
        for(int i = 0; i < k; ++i)
        {
            if(x >> i & 1)
            {
                ++p;
                t -= n[i];
            }
        }
        t -= (p + 1);
        if(t < 0 || t < k - 1) continue;
        if(p & 1)
            ans = (ans - C(t, k - 1, MOD) + MOD) % MOD;
        else
            ans = (ans + C(t, k - 1, MOD)) % MOD;
    }
    return (ans + MOD) % MOD;
}

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    for(int i = 1; i <= N; ++i)
        cin >> A[i - 1];

    init(N);

    int ans = multiple_combination(A, M, MOD);
    cout << ans << endl;
}
Share