『算法-ACM竞赛-数学-数论』容斥定理完全解析（转）

『算法-ACM 竞赛-数学-数论』容斥定理完全解析（转）

数学–数论–容斥定理完全解析（转）

对容斥原理的描述

容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。

描述

容斥原理可以描述如下：

要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。

关于集合的原理公式

上述描述的公式形式可以表示如下：

** **

它可以写得更简洁一些，我们将 B 作为所有 Ai 的集合，那么容斥原理就变成了：

这个公式是由 De Moivre (Abraham de Moivre)提出的。

关于维恩图的原理

用维恩图来表示集合 A、B 和 C：

那么的面积就是集合 A、B、C 各自面积之和减去 , , 的面积，再加上的面积。

由此，我们也可以解决 n 个集合求并的问题。

关于概率论的原理

设事件，代表发生某些事件的概率（即发生其中至少一个事件的概率），则：

这个公式也可以用 B 代表 Ai 的集合：

容斥原理的证明

我们要证明下面的等式：

其中 B 代表全部 Ai 的集合

我们需要证明在 Ai 集合中的任意元素，都由右边的算式被正好加上了一次（注意如果是不在 Ai 集合中的元素，是不会出现在右边的算式中的）。

假设有一任意元素在 k 个 Ai 集合中（k>=1），我们来验证这个元素正好被加了一次：

当 size(C)=1 时，元素 x 被加了 k 次。

当 size(C)=2 时，元素 x 被减了 C(2,k)次，因为在 k 个集合中选择 2 个，其中都包含 x。

当 size(C)=3 时，元素 x 被加了 C(3,k)次。

……

当 size(C)=k 时，元素 x 被加/减了 C(k,k)次，符号由 sign(-1)^(k-1)决定。

当 size(C)>k 时，元素 x 不被考虑。

然后我们来计算所有组合数的和。

由二项式定理，我们可以将它变成：

我们把 x 取为 1，这时表示 1-T（其中 T 为 x 被加的总次数），所以，证明完毕。

对于实际问题的应用

容斥原理的理论需要通过例子才能很好的理解。

首先，我们用三个简单的例子来阐释这个理论。然后会讨论一些复杂问题，试看如何用容斥原理来解决它们。

其中的“寻找路径数”是一个特殊的例子，它反映了容斥问题有时可以在多项式级复杂度内解决，不一定需要指数级。

一个简单的排列问题

由 0 到 9 的数字组成排列，要求第一个数大于 1，最后一个数小于 8，一共有多少种排列？

我们可以来计算它的逆问题，即第一个元素<=1 或者最后一个元素>=8 的情况。

我们设第一个元素<=1 时有 X 组排列，最后一个元素>=8 时有 Y 组排列。那么通过容斥原理来解决就可以写成：

经过简单的组合运算，我们得到了结果：

然后被总的排列数 10!减，就是最终的答案了。

（0,1,2）序列问题

长度为 n 的由数字 0，1，2 组成的序列，要求每个数字至少出现 1 次，这样的序列有多少种？

同样的，我们转向它的逆问题。也就是不出现这些数字的序列不出现其中某些数字的序列。

我们定义 Ai(i=0…2)表示不出现数字 i 的序列数，那么由容斥原理，我们得到该逆问题的结果为：

可以发现每个 Ai 的值都为 2^n（因为这些序列中只能包含两种数字）。而所有的两两组合都为 1（它们只包含 1 种数字）。最后，三个集合的交集为 0。（因为它不包含数字，所以不存在）

要记得我们解决的是它的逆问题，所以要用总数减掉，得到最终结果：

方程整数解问题

给出一个方程：

其中。

求这个方程的整数解有多少组。

我们先不去理会 xi<=8 的条件，来考虑所有正整数解的情况。这个很容易用组合数来求解，我们要把 20 个元素分成 6 组，也就是添加 5 块“夹板”，然后在 25 个位置中找 5 块“夹板”的位置。

然后通过容斥原理来讨论它的逆问题，也就是 x>=9 时的解。

我们定义 Ak 为 xk>=9 并且其他 xi>=0 时的集合，同样我们用上面的添加“夹板”法来计算 Ak 的大小，因为有 9 个位置已经被 xk 所利用了，所以：

然后计算两个这样的集合 Ak、Ap 的交集：

因为所有 x 的和不能超过 20，所以三个或三个以上这样的集合时是不能同时出现的，它们的交集都为 0。最后我们用总数剪掉用容斥原理所求逆问题的答案，就得到了最终结果：

求指定区间内与 n 互素的数的个数：

给出整数 n 和 r。求区间[1;r]中与 n 互素的数的个数。

去解决它的逆问题，求不与 n 互素的数的个数。

考虑 n 的所有素因子 pi(i=1…k)

在[1;r]中有多少数能被 pi 整除呢？它就是：

然而，如果我们单纯将所有结果相加，会得到错误答案。有些数可能被统计多次（被好几个素因子整除）。所以，我们要运用容斥原理来解决。

我们可以用 2^k 的算法求出所有的 pi 组合，然后计算每种组合的 pi 乘积，通过容斥原理来对结果进行加减处理。

关于此问题的最终实现：

 


int solve(int n, int r)
{

    vector<int> p;
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0)
        {
            p.push_back(i);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)  p.push_back(n);

    int sum = 0;

    for (int msk = 1; msk < (1 << p.size()); ++msk)
    {
        int mult = 1,

            bits = 0;

        for (int i = 0; i < (int)p.size(); ++i)
            if (msk & (1 << i)){
                ++bits;
                mult *= p[i];
            }

        int cur = r / mult;

        if (bits % 2 == 1)
            sum += cur;
        else
            sum -= cur;
    }
    return r - sum;
}
TEXT

算法的复杂度为。

求在给定区间内，能被给定集合至少一个数整除的数个数

给出 n 个整数 ai 和整数 r。求在区间[1;r]中，至少能被一个 ai 整除的数有多少。

解决此题的思路和上题差不多，计算 ai 所能组成的各种集合（这里将集合中 ai 的最小公倍数作为除数）在区间中满足的数的个数，然后利用容斥原理实现加减。

此题中实现所有集合的枚举，需要 2^n 的复杂度，求解 lcm 需要 O(nlogr)的复杂度。

能满足一定数目匹配的字符串的个数问题

给出 n 个匹配串，它们长度相同，其中有一些’?’表示待匹配的字母。然后给出一个整数 k，求能正好匹配 k 个匹配串的字符串的个数。更进一步，求至少匹配 k 个匹配串的字符串的个数。

首先我们会发现，我们很容易找到能匹配所有匹配串的字符串。只需要对比所有匹配串，去在每一列中找出现的字母（或者这一列全是’?’，或者这一列出现了唯一的字母，否则这样的字符串就存在），最后所有字母组成的单词即为所求。

现在我们来学习如何解决第一个问题：能正好匹配 k 个匹配串的字符串。

我们在 n 个匹配串中选出 k 个，作为集合 X，统计满足集合 X 中匹配的字符串数。求解这个问题时应用容斥原理，对 X 的所有超集进行运算，得到每个 X 集合的结果：

此处 f(Y)代表满足匹配集合 Y 的字符串数。

如果我们将所有的 ans(X)相加，就可以得到最终结果：

这样，就得到了一个复杂度的解法。

这个算法可以作一些改进，因为在求解 ans(X)时有些 Y 集合是重复的。

回到利用容斥原理公式可以发现，当选定一个 Y 时，所有中 X 的结果都是相同的，其符号都为。所以可以用如下公式求解：

这样就得到了一个复杂度的解法。

现在我们来求解第二个问题：能满足至少k 个匹配的字符串有多少个。

显然的，我们可以用问题一的方法来计算满足 k 到 n 的所有结果。问题一的结论依然成立，不同之处在于这个问题中的 X 不是大小都为 k 的，而是>=k 的所有集合。

如此进行计算，最后将 f(Y)作为另一个因子：将所有的 ans 做和，有点类似二项式展开：

在《具体数学》( Graham, Knuth, Patashnik. “Concrete Mathematics” [1998] )中，介绍了一个著名的关于二项式系数的公式：

根据这个公式，可以将前面的结果进行化简：

那么，对于这个问题，我们也得到了一个的解法：

路径的数目问题

在一个的方格阵中，有 k 个格子是不可穿越的墙。一开始在格子(1,1)（最左下角的格子）中有一个机器人。这个机器人只能向上或向右行进，最后它将到达位于格子(n,m)的笼子里，其间不能经过障碍物格子。求一共有多少种路线可以到达终点。

为了方便区分所有障碍物格子，我们建立坐标系，用(x,y)表示格子的坐标。

首先我们考虑没有障碍物的时候：也就是如何求从一个点到另一个点的路径数。如果从一个点在一个方向要走 x 个格子，在另一个方向要走 y 个格子，那么通过简单的组合原理可以得知结果为：

现在来考虑有障碍物时的情况，我们可以利用容斥原理：求出至少经过一个障碍物时的路径数。

对于这个例子，你可以枚举所有障碍物的子集，作为需要要经过的，计算经过该集合障碍物的路径数（求从原点到第一个障碍物的路径数、第一个障碍物到第二个障碍物的路径数…最后对这些路径数求乘积），然后通过容斥原理，对这些结果作加法或减法。

然而，它是一个非多项式的解法，复杂度。下面我们将介绍一个多项式的解法。

我们运用动态规划：令 d[i][j]代表从第 i 个点到第 j 个点，不经过任何障碍物时的路径数（当然除了 i 和 j）。那么我们总共需要 k+2 个点，包括 k 个障碍物点以及起点和终点。

首先我们算出从 i 点到 j 点的所有路径数，然后减掉经过障碍物的那些“坏”的路线。让我们看看如何计算“坏”的路线：枚举 i 和 j 之间的所有障碍物点 i<l<j，那么从 i 到 j 的“坏”路径数就是所有 d[i][l]和 d[l][j]的乘积最后求和。再被总路径数减掉就是 d[i][j]的结果。

我们已经知道计算总路径数的复杂度为，那么该解法的总复杂度为。

（译注：当然也有 O(nm)的 dp 解法，根据 n、m、k 的值可以采取适当的解法）

素数四元组的个数问题

给出 n 个数，从其中选出 4 个数，使它们的最大公约数为 1，问总共有多少中取法。

我们解决它的逆问题：求最大公约数 d>1 的四元组的个数。

运用容斥原理，将求得的对于每个 d 的四元组个数的结果进行加减。

其中 deg(d)代表 d 的质因子个数，f(d)代表四个数都能被 d 整除的四元组的个数。

求解 f(d)时，只需要利用组合方法，求从所有满足被 d 整除的 ai 中选 4 个的方法数。

然后利用容斥原理，统计出所有能被一个素数整除的四元组个数，然后减掉所有能被两个素数整除的四元组个数，再加上被三个素数整除的四元组个数…

和睦数三元组的个数问题

给出一个整数。选出 a, b, c (其中 2<=a<b<c<=n)，组成和睦三元组，即：

· 或者满足，，

·或者满足

首先，我们考虑它的逆问题：也就是不和睦三元组的个数。

然后，我们可以发现，在每个不和睦三元组的三个元素中，我们都能找到正好两个元素满足：它与一个元素互素，并且与另一个元素不互素。

所以，我们只需枚举 2 到 n 的所有数，将每个数的与其互素的数的个数和与其不互素的数的个数相乘，最后求和并除以 2，就是要求的逆问题的答案。

现在我们要考虑这个问题，如何求与 2 到 n 这些数互素（不互素）的数的个数。虽然求解与一个数互素数的个数的解法在前面已经提到过了，但在此并不合适，因为现在要求 2 到 n 所有数的结果，分别求解显然效率太低。

所以，我们需要一个更快的算法，可以一次算出 2 到 n 所有数的结果。

在这里，我们可以使用改进的埃拉托色尼筛法。

·首先，对于 2 到 n 的所有数，我们要知道构成它的素数中是否有次数大于 1 的，为了应用容斥原理，我们还有知道它们由多少种不同的素数构成。

对于这个问题，我们定义数组 deg[i]：表示 i 由多少种不同素数构成，以及 good[i]：取值 true 或 false，表示 i 包含素数的次数小于等于 1是否成立。

再利用埃拉托色尼筛法，在遍历到某个素数 i 时，枚举它在 2 到 n 范围内的所有倍数，更新这些倍数的 deg[]值，如果有倍数包含了多个 i，那么就把这个倍数的 good[]值赋为 false。

·然后，利用容斥原理，求出 2 到 n 每个数的 cnt[i]：在 2 到 n 中不与 i 互素的数的个数。

回想容斥原理的公式，它所求的集合是不会包含重复元素的。也就是如果这个集合包含的某个素数多于一次，它们不应再被考虑。

所以只有当一个数 i 满足 good[i]=true 时，它才会被用于容斥原理。枚举 i 的所有倍数 ij，那么对于 ij，就有 N/i 个与 i*j 同样包含 i（素数集合）的数。将这些结果进行加减，符号由 deg[i]（素数集合的大小）决定。如果 deg[i]为奇数，那么我们要用加号，否则用减号。

程序实现：

 
TEXT

 int n;
TEXT

bool good[MAXN];

int deg[MAXN], cnt[MAXN];

long long solve() {

      memset (good, 1, sizeof good);

      memset (deg, 0, sizeof deg);

      memset (cnt, 0, sizeof cnt);



      long long ans_bad = 0;

      for (int i=2; i<=n; ++i) {

              if (good[i]) {

                       if (deg[i] == 0) deg[i] = 1;

                       for (int j=1; i*j<=n; ++j) {

                                if (j > 1 && deg[i] == 1)

                                         if (j % i == 0)

                                                 good[i*j] = false;

                                         else

                                                 ++deg[i*j];

                                cnt[i*j] += (n / i) * (deg[i]%2==1 ? +1 : -1);

                       }

              }

              ans_bad += (cnt[i] - 1) * 1ll * (n - cnt[i] - 1);

      }

      return (n-1) * 1ll * (n-2) * (n-3) / 6 - ans_bad / 2;
TEXT

}

最终算法的复杂度为，因为对于大部分 i 都要进行 n/i 次枚举。

错排问题

我们想要证明如下的求解长度为 n 序列的错排数的公式：

它的近似结果为：

（此外，如果将这个近似式的结果向其最近的整数舍入，你就可以得到准确结果）

我们定义 Ak：在长度为 n 的序列中，有一个不动点位置为 k(1<=k<=n)时的序列集合。

现在我们运用容斥原理来计算至少包含有一个不动点的排列数，要计算这个，我们必须先算出所有 Ak、以及它们的交集的排列数。

因为我们知道当有 x 个不动点时，所有不动点的位置是固定的，而其它点可以任意排列。

用容斥原理对结果进行带入，而从 n 个点中选 x 个不动点的组合数为，那么至少包含一个不动点的排列数为：

那么不包含不动点（即错排数）的结果就是：

化简这个式子，我们得到了错排数的准确式和近似式：

（因为括号中是的泰勒展开式的前 n+1 项）

用这个式子也可以解决一些类似的问题，如果现在求有 m 个不动点的排列数，那么我们可以对上式进行修改，也就是将括号中的累加到 1/n!改成累加到 1/(n-m)!。

题目描述

求 1 到 n 范围内能被 5，6，8 整除的数的个数。（0<n<10^7）输入

多组数据，处理到文件结尾。

每行输入一个 n；

输出

输出结果，每个结果占一行。

示例输入

1000
TEXT

示例输出

400



    #include <iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int main()
    {
        int i,j,k,n,b,a;
        while(cin>>n)
        {
            b = n/30+n/24+n/40;
        a = n/120;
        k = n/5+n/6+n/8;
        cout<<k-b+a<<endl;
        }

        return 0;
    }
TEXT