容斥原理 | Messy

POJ3904 & more

初步理解

参见上图，集合$A$,$B$,$C$都是有限集，比如A是一个班里会跳舞的人的集合，B是一个班里会唱歌的人的集合，C是一个班里搞ACM的人的集合，并且已知这些人的数量，以及既会xx又会xx的人的数量，求会三样中至少一样的人的数量，显然

$$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$$

公式化

$$ {\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|={}&\sum _{i=1}^{n}|A_{i}|-\sum _{1\leq i运用De Morgan律，有：

—维基百科就先抄到这里—

解释一下公式

这里解释的是运用De Morgan律之后的公式。（也就是既不会xx又不会xx，连xx都不会的人的数量）
$S$表示的是一个有限元素的集合，$A_i$表示的是$S$中具有性质$P_i$的元素的集合。现在要求的是$S$中不具备任何一个罗列出的性质的元素的个数。首先我们在$S$中去掉具有性质$P_1$的元素，再去掉具有性质$P_2$的元素，再去掉……然后我们发现我们把即具有$P_1$又具有$P_2$的元素减掉了两次，这时候我们把它们（具有两种元素的那些）加回来，发现后面又多加了，再减去具有三种性质的集合……以此类推。

证明

这里简单的阐述一下：考虑一个在所有m个性质中具有n个性质的元素y，计算y对式(2)右边的贡献，运用二项式定理（$(1−1)^n=0: n≠0$）得0。所以任何至少具有1个性质的元素对式(2)右边的贡献都是0，容斥原理得证。

一个小问题

题面

n个人站成一队，现在要对这n个人进行重排列，使得新队伍中每个人前面的人都不是原队伍中排在自己前面的那个人。求这样重排列的方案数。
例如n=3，原来的排列是123，现在的可行排列是213，132，321这样三种。
即，令原排列为{1,2,3,…,n}，新排列中不允许任意相邻位出现i,(i+1)这样的形式。

Sample

输入n,输出合法排列数$Q_n$。

input	1	2	3	4
output	1	1	3	11

解答

$Q_n=n!-\binom{n-1}{1}(n-1)!+\binom{n-1}{2}(n-2)!-\binom{n-1}{3}(n-3)!+...+(-1)^{n-1}\binom{n-1}{n-1}1!$ （待补充）

POJ3904

题意

给n个数$a[1…n]$，取其中4个数，使得gcd为1，求这样的取法总数。

(1 ≤ n ≤ 10000)

Sample input

4 		//n
2 3 4 5 //a[1...n]
4
2 4 6 8 
7
2 3 4 5 7 6 8

Sample Output

1
2
3

1 
0 
34

解法

考虑问题的反面，即gcd不为1的情况。令性质$A_i : gcd(x_1, x_2, x_3, x_4)=p_i$，其中$p_i$是在$a[1…n]$中取得的质因数。若有$k$个数具有质因数$p_i$,则$|A_i|=\binom{k}{4}$。我们可使用公式：

$$ {\displaystyle {\begin{aligned}&\left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|\\={}&|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leq i举例来说，对于${2,4,6,8,9}$这几个数，我们可以取得$p_1=2$，并且有4个数具有质因数2，则$|A_1|=\binom{4}{4}=1$。也可以取得$p_2=3$，有2个数具有质因数3，则$|A_2|=0$。核心在于使用容斥原理去重，比如有k个数同时具有质因数2和3，那这部分是已经计数的了，需要减去。是加是减取决于当前考虑的质因数的个数。

代码

int p[MAXN];
int sum[MAXN];
int primeCnt[MAXN];
long long C_4[MAXN];
void getC(){
    memset(p, 0, sizeof(p));
    for (long long i = 0; i < MAXN; ++i) {
        if (i < 4) {
            C_4[i] = 0;
        }
        else C_4[i] = i * (i - 1) * (i - 2) * (i - 3) / 24;
    }
}
void func(int n){
    int r = 0;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            p[r++] = i;
            while (n % i == 0){
                n /= i;
            }
        }
    }
    if (n != 1) p[r++] = n;
    for (int i = 1; i < (1 << r); ++i) {
        int c = 1, t = 0;
        for (int j = 0; j < r; ++j) {
            if (i & (1 << j)) c *= p[j], t++;
        }
        sum[c]++;
        primeCnt[c] = t;
    }
    return;
}
int main(){
    getC();
    int n;
    while (~scanf("%d", &n)) {
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n; ++i) {
            int m;
            scanf("%d", &m);
            func(m);
        }
        long long tot = 0;
        for (int i = 0; i < MAXN; ++i) {
            if (sum[i]) {
                if (primeCnt[i] % 2 == 0) {
                    tot -= C_4[sum[i]];
                } else tot += C_4[sum[i]];
            }
        }
        tot = C_4[n] - tot;
        printf("%lld\n", tot);
    }
}

2014 Regional 西安 F题

题面

Portal

http://codeforces.com/gym/100548

题面PDF

n朵花排成一排，先在要从m种颜色中选取k种颜色，来给这n多花染色，相邻的花不同色，并且恰好使用这k种颜色。求这样的方案数（mod $10^9+7$）。

$(1 ≤ n,m ≤ 10^9, 1 ≤ k ≤ 10^6, k ≤ n,m)$

思路

如果不考虑要“恰好”使用这k种颜色，那么方案数是$k·(k-1)^{n-1}$（可以这样考虑：第一朵花有k种颜色可选，第二朵花有k-1种，第三朵花同理……）。那么怎么得到恰好k种颜色的染色方案数？

有种思路是：求出使用$k-1$种颜色的方案数，然后减去，就得到答案。

显然这种思路是有问题的，问题在于并没有确定使用哪几种颜色，并且减去的方案中有重叠。

那就去重咯。去重就想到容斥原理咯。

整理了一下思路后，我们可以这么定义$A_i$：所选颜色中不含有第i种颜色。接下来就是使用容斥原理去重了。

$$ \begin{align*} ANSWER&=S-\sum_{2}^{k-1}(-1)^{k-i}\binom{k}{i}i(i-1)^{n-1}\\ &=k·(k-1)^{n-1}-\sum_{2}^{k-1}(-1)^{k-i}\binom{k}{i}i(i-1)^{n-1} \end{align*} $$