数组合数学

容斥计数：N个集合的情况

字数统计: 2.6k字   |   阅读时长: 11分
, , ,

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

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

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

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

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

集合个数变多后，容斥原理的实现难度会变大，本文我们通过 (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;
}

3116. 单面值组合的第 K 小金额

给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。

你有无限量的每种面额的硬币。但是，你 不能 组合使用不同面额的硬币。

返回使用这些硬币能制造的 第 kth 小 金额。

提示：

1
2
3
4
1 <= coins.length <= 15
1 <= coins[i] <= 25
1 <= k <= 2 * 1e9
coins 包含两两不同的整数。

示例 1：
输入： coins = [3,6,9], k = 3
输出： 9
解释：给定的硬币可以制造以下金额：
3元硬币产生3的倍数：3, 6, 9, 12, 15等。
6元硬币产生6的倍数：6, 12, 18, 24等。
9元硬币产生9的倍数：9, 18, 27, 36等。
所有硬币合起来可以产生：3, 6, 9, 12, 15等。

示例 2：
输入：coins = [5,2], k = 7
输出：12
解释：给定的硬币可以制造以下金额：
5元硬币产生5的倍数：5, 10, 15, 20等。
2元硬币产生2的倍数：2, 4, 6, 8, 10, 12等。
所有硬币合起来可以产生：2, 4, 5, 6, 8, 10, 12, 14, 15等。

算法：值域二分 + 容斥原理

值域二分

由于 $k$ 非常大，直接求出第 $k$ 小金额很难。但是给定一个金额 $m$，有多少种金额不大于 $m$ 相对比较容易，记其答案为 $a$，随着 $m$ 增大，$a$ 也增大，因此可以考虑二分答案。

若 $a < k$，则 $m$ 肯定是小了，将 $left$ 置为 $m + 1$ 继续，否则，将 $right$ 置为 $m$ 继续。

容斥原理

下面考虑给定金额 $m$ 后，能组出的不大于 $m$ 的金额有多少种。大方向是枚举 coins 种的每种面额 $c$，其对应的比 $m$ 小的金额数为：

但这里还有个问题，就是一种金额可能会在多种面额中被取到，比如金额 16 可能在面额为 2 的金额清单中取到，也可以在面额为 4 的清单中取到。

这样在把 $\left\lfloor\frac{m}{2}\right\rfloor$ 和 $\left\lfloor\frac{m}{4}\right\rfloor$ 中可能重复取到 16 这种金额。

对于 2 个面额 $c_{i}, c_{j}$，其最小公倍数为 $l = lcm(c_{i}, c_{j})$，那么 $l, 2l, 3l, \cdots$ 都是计了两次的。

例如对于 8 和 12 两种面额，最小公倍数为 $lcm(12, 8) = 24$，于是 $24, 48, \cdots$ 为这两种面额的金额清单中都会出现的：

1
2
12 24 36 48
8 16 24 32 40 48

当我们在答案中加上 $\left\lfloor\frac{m}{c_{i}}\right\rfloor + \left\lfloor\frac{m}{c_{j}}\right\rfloor$ 后，还需要把重复计数的 $\left\lfloor\frac{m}{lcm(c_{i}, c_{j})}\right\rfloor$ 加回来。

以此类推，对于 $t$ 种面额 $c_{i_{1}}, c_{i_{2}}, \cdots, c_{i_{i_{t}}}$，其最小公倍数 $l = lcm(c_{i_{1}}, c_{i_{2}}, \cdots, c_{i_{i_{t}}})$，这样 $l, 2l, \cdots$ 这些金额都是计了 $t$ 次的。

上述这些重复计数的情况，需要通过容斥原理抹平，结果公式如下：

整理后，我们得到，比 $m$ 小的金额的种类数为：

实现以上公式的方法通过位运算枚举子集，具体就是枚举 $x \in [1, 2^{n}-1]$，$x$ 在二进制下共有 $t$ 位为 1，设其分别为 $i_{1}, i_{2}, \cdots, i_{t}$，那么当前 $x$ 对应于结果公式中的一项，如下：

最后考虑二分初始时的上下界，对于下界，可以取 $k-1$，对于上界，可以取 $\min(coins) \times k$。

预处理子集最小公倍数

由于每个子集的最小公倍数在二分过程中每次检查时都需要用到，可以预处理出来。预处理的过程是一个动态规划过程，依次枚举 coins，枚举到 coins[i] 时，由 coins[0..i-1] 构成的所有子集都已经预处理完成，这些已经预处理完成的子集由整数 0, 1, 2, ..., (1 << i) - 1 表示，枚举 j = 0,1,...,(1 << i) - 1，做如下更新：

1
subset_lcm[j | (1 << i)] = lcm(subset_lcm[j], coins[i])

时间复杂度

subset_lcm 共 $2^{n}$ 个位置，每个位置的更新需要 $\log U$，因此预处理时间复杂度为 $O(2^{n}\log U)$。

预处理之后，二分的每一次检查的时间复杂度为 $n2^{n}$，共检查 $O(\log kU)$ 次。总时间复杂度 $O(2^{n}\log kU)$，其中 $U$ 为 coins 中的值的大小。

代码 (Python，模板)

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
class Solution:
    def findKthSmallest(self, coins: List[int], k: int) -> int:
        n = len(coins)
        subset_lcm  = [1] * (2 ** n)
        for i in range(n):
            for j in range(1 << i):
                subset_lcm[j | (1 << i)] = math.lcm(subset_lcm[j], coins[i])

        def check(m):
            ans = 0
            for x in range(1, 1 << n):
                t = x.bit_count()
                if t % 2 == 1:
                    ans += m // subset_lcm[x]
                else:
                    ans -= m // subset_lcm[x]
            return ans

        left = k - 1
        right = min(coins) * k

        while left < right:
            mid = (left + right) // 2
            a = check(mid)
            if a < k:
                left = mid + 1
            else:
                right = mid

        return left
Share