这篇文章上次修改于 284 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记(11): 容斥原理的简单应用

容斥原理

容斥原理本身易于理解，实际上是减去重复计算的部分的思想。

类似于两个有交集的集和并集，就是两个集合相加减去交集。

容斥模型概念

全集：各种元素不在属性限制的条件下的种类数
元素：不同的变量，被限制的个体单元
属性：限制条件。
所求的解：所有变量满足对应属性时集合的大小

不定方程非负整数解计数

给你n个变量x，说明了每个x的约束条件，例如x < m, 又说明了所有x的总和值为S，求不同解的个数。即 x1 + x2 + x3 +…. + xn = S, (x1 < m1 , x2 < m2, x3 < m3……xn < mn)

如果没有约束条件：

对于原本的问题解，我们可以使用割板法，也就是排列组合即可，类似于分10个苹果给4个小朋友。

使用组合模型便可获取有f(S)代表到当总量为S时，有多少种分配方法。

但有约束条件的情况下，不妨将题目抽象为容斥模型：

当总量为S，设定 g(i) 代表 xi 在约束条件下，其它任意的种类数，可得g(i) = f(S) - f(S - (mi + 1) * xi), 意思就是所有情况减去xi超限的情况，xi超限情况只要直接让S预留mi + 1 个 x1的所有情况就是g(i)

此时我们我们得到的g(i) 就是满足第一个，但其他不满足的情况，如果我们将他们相加，就需要减去两个符合条件其他不符合，然后处理三个，在处理四个。这就是容斥经典模型。

[HAOI2008] 硬币购物

共有 4 种硬币。面值分别为 c1, c2, c3, c4。

某人去商店买东西，去了 n 次，对于每次购买，他带了 di 枚 i 种硬币，想购买 s 的价值的东西。请问每次有多少种付款方法。

思路同上，此时我们如何计算没有限制条件的组数，也就是任意数量能满足的种数：完全背包。

达成之后，就进行容斥即可。

题目思想突破口在于只有四种硬币，如果使用容斥定理，我们就需要2^4 - 1个情况考虑，四种而不是上百上千种硬币大大利好了容斥。

code:

#include<bits/stdc++.h>

using namespace std;
using i64 = long long;
const int maxN = 1e5 + 5;

void solve(){
    vector<i64> value(5);
    i64 n;
    for(int i = 1; i <= 4; i++)
        cin >> value[i];
    cin >> n;

    vector<i64> numOfSum(maxN);
    numOfSum[0] = 1;
    for(int type = 1; type <= 4; type++){
        for(int S = 1; S < maxN; S++){
            if(S - value[type] >= 0)
                numOfSum[S] += numOfSum[S - value[type]];
        }
    }
    vector<i64> maxCoin(5);
    while(n--){
        i64 Sum;
        i64 result = 0;
        cin >> maxCoin[1] >> maxCoin[2] >> maxCoin[3] >> maxCoin[4] >> Sum;
        for(int group = 1; group < 16; group++){
            i64 tmp = Sum, bits = 0;
            for(int j = 1; j <= 4; j++){
                if((group >> (j - 1)) % 2 == 1){
                    tmp -= (maxCoin[j] + 1) * value[j];
                    bits++;
                }
            }
            if (tmp >= 0)
                result += (bits % 2 * 2 - 1) * numOfSum[tmp];
        }
        cout << numOfSum[Sum] - result << endl;
    }
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T = 1;
    while(T--){
        solve();
    }
}

数论

最大公约数问题

例如：有1≤ x, y ≤ N , 设 f(k) 为最大公约数为 k 的数对个数，求f(1) ~ f(N)；

找到最大公约数特征的容斥原理模型，什么会是有重叠的。

例如我们可以很轻松的找到以两个数都是 k 的倍数的数对，这个数对的GCD也就肯定是k的倍数。

我们记这样的数对个数为 g(k) ; g(k) 是很容易获取的；同时我们可以发现

f(k) = g(k) - f(2k) - f(3k) - f(4k) ….

因此我们就可以倒过来从后往前计算得到f(k) - f(1)的值

code:

for (long long k = N; k >= 1; k--) {
  f[k] = (N / k) * (N / k); // g(k) = (N / k) * (N / k)
  for (long long i = k + k; i <= N; i += k) f[k] -= f[i];
}

再例如给定序列 a1-n，求非空集和GCD为1 的数量；

设置答案 f(k) 表示GCD为k的非空集和数量。

同样我们可以设g(k) 为 GCD为 K的倍数的非空集和数量，设序列中K的倍数有t个也就是2^t个；

同时，我们也可以发现：

f(k) = g(k) - f(2 * k) - f(3 * k) - f(4 * k) …

同样可以倒过来计算得出。

code:

for(int i = 1; i < 1e6 + 10; i++){
    int sum = 0;
    for(int j = i; j < 1e6 + 10; j += i){
        sum += cnt[j]; // cnt 也就是 序列中数字j的个数
    }
    res[i] = pow2[sum] - 1;
}

for(int i = 1e6 + 10; i > 0; i--){
    for(int j = 2 * i; j < 1e6 + 10; j+= i){
        res[i] = (res[i] - res[j] + MOD) % MOD;
    }
}

这种gcd还会很隐蔽的被具体化成实际的二维图像：例如一个n*n点阵，如果两个点之间的xy轴差值gcd=1就代表两个点之间的线段没有遇到其他点。

Mai Icy