容斥原理

定理

集合

实质

\sum i = 0 n (- 1) i (n i) = [n = 0] "> \sum i = 0 n (? 1) i (n i ) = [ n = 0 ]

也就是上面的证明过程

错排

满足

D n = n! \sum i = 0 n (- 1) i i! "> D n = n! \sum i = 0 n ( ? 1 ) i i !

还有一个递推关系

总结

在统计一类问题时，应用容斥原理可以有效的弱化限制条件
有一种统计恰好k个的问题，限制很强，通常弱化为先拿出k个，剩下的任意
这时候容斥的形式通常是

= \geq k 个 - \geq k + 1 个 + \geq k + 2 个 . . . "> = \geq k 个 ? \geq k + 1 个 + \geq k + 2 个 . . .

这时候我们在统计

有的问题是恰好没有之类的，这时候

update 2017.5.3:貌似这个东西也不是这么回事儿...感觉还与二项式反演有关...还是具体问题具体分析吧

**update 2017.5.15**

今天~~闲来无事~~证明了一下，这玩意应该是普遍成立的！

我们考虑一个恰好

(1) = \sum i = k x (- 1) i - k (i k) (x i) (2) = (x k) \sum i = k x (- 1) i - k (x - k x - i) (3) = (x k) \sum j = 0 x - k (x - k j) (4) = [x == k] ">

哈哈O(∩_∩)O

莫比乌斯反演 Mobius Inversion

说明

容斥原理是莫比乌斯反演在有限偏序集上的一个实例
莫比乌斯反演应用在一类二变量函数，偏序关系到实数的映射
《组合数学》上讨论了好多任意有限偏序集的莫比乌斯反演，还有偏序集的直积，我已经看蒙了
所以直接说莫比乌斯反演在数论上的经典形式吧，~~反正不是整除关系也不会考~~

积性函数

定义

定义域为正整数集的函称为数论函数

满足

完全积性函数对ab没有互质限制

积性函数：

完全积性函数：

单位函数
恒等函数
常函数

狄利克雷卷积

(f * g) (n) = \sum d | n f (d) g (n d) "> (f ? g) (n) = \sum d | n f (d) g (n d )

满足交换律，结合律，对加法的分配律，单位元

###性质 1. 积性函数的**点积**和**狄利克雷卷积**也是积性函数 2. 一个函数的约数和可以卷上

计算

可以
线性筛

i=1, i是质数和i%p[j]!=0的情况很好求
对于i%p[j] == 0,可以通过分析增加一个最小质因子后的变化，或者直接考虑
也可以筛出最小质因子的次数，分解成
一些非积性函数也可以通过分析函数的性质也可以用线性筛来求
例：欧拉函数可以直接根据公式得到如何处理

void sieve() {
	varphi[1] = 1;
	for(int i=2; i<=n; i++) {
		if(!notp[i]) p[++p[0]] = i, varphi[i] = i-1;
		for(int j=1; j<=p[0] && i*p[j]<=n; j++) {
			notp[i*p[j]] = 1;
			if(i%p[j] == 0) {
				varphi[i*p[j]] = varphi[i] * p[j];
				break;
			}
			varphi[i*p[j]] = varphi[i] * (p[j]-1);
		}
	}
	for(int i=1; i<=n; i++) varphi[i] += varphi[i-1];
}

μ (1) = 1 μ (n) = (- 1) i n 是 i 个 质 数 之 积 μ (n) = 0 p 2 | n, p > 1 "> μ (1) = 1

μ * 1 = ϵ ， 即 \sum d | n μ (d) = [n = 1] $ $ 。 < / b r > $ P r o o f . $ 设 $ n $ 有 $ k $ 种 质 因 子 ， "> μ ? 1 = ? ， 即 \sum d | n μ (d) = [n = 1] $ $ 。 < / b r >

\sum\limits_{d|n}\mu(d) = \sum_{i=0}^{k}(-1)i\binom{k}{i}

和上面的容斥原理证明类似，应用二项式定理</br>## 欧拉函数 "> 和上面的容斥原理证明类似，应用二项式定理 ## 欧拉函数

\varphi(n) = \sum_{i=1}^n [(n,i)=1] \
\varphi(n) = \prod p^{c-1}(p-1)

< / b r > 1. $ $ φ * 1 = i d 即 n = \sum d | n φ (d), 反 演 后 μ * i d = φ "> < / b r > 1. $ $ φ ? 1 = i d 即 n = \sum d | n φ (d), 反 演

$\sum i = 1 n [(n, i) = 1] * i = [n = 1] + n * φ (n) 2 "> \sum i = 1 n [(n, i) = 1] ? i = [ n = 1 ] + n ? φ ( n ) 2$

莫比乌斯反演

g (n) = \sum d | n f (d) f (n) = \sum d | n μ (d) g (n d) "> g (n) = \sum d | n f (d)

g (n) = \sum n | d f (n) f (n) = \sum n | d μ (d) g (d n) "> g (n) = \sum n | d f (n)

应用

感觉还是直接使用这个式子代换比较简单，构造函数再进行反演好像并不好想

\sum d | n μ (d) = [n = 1] "> \sum d | n μ (d) = [n = 1]

有一些常见技巧:

枚举gcd取值
交换枚举倍数与约数
用莫比乌斯函数求和替换
改写求和指标
最后通常需要得到一个可以整除分块的形式，处理一个函数的前缀和后可以在根号复杂度内解决一次询问

一般的题目推导起来挺套路的，通常都是枚举两个变量求一个带着gcd的东西(有的题目需要你自己把式子变形把gcd放进去)，套路推♂倒之后都变成了整除分块，然后重点就在如何通过线性筛求函数了

栗子

\sum i = 1 n \sum j = 1 m g c d (i, j) = \sum d = 1 n d \sum i = 1 n \sum j = 1 m [g c d (i, j) = d] 先 枚 举 d 再 枚 举 倍 数, 出 现 [= 1] 的 形 式 = \sum d = 1 n d \sum i = 1 n d \sum j = 1 m d [g c d (i, j) = 1] 用 \sum e | n μ (e) = [n = 1] 替 换, 先 枚 举 e 再 枚 举 倍 数 = \sum d = 1 n d \sum e = 1 n μ (e) n d e m d e 改 写 求 和 指 标 ， 令 D = d e = \sum D = 1 n \sum d | D d μ (D d) n D m D 发 现 最 后 就 是 i d * μ = φ = \sum D = 1 n φ (D) n D m D "> \sum i = 1 n \sum j = 1 m g c d (i, j) 先 枚 举 d 再 枚 举

代码

int notp[N], p[N];ll varphi[N];
void sieve(int n) {
    varphi[1]  1;
    for(in i=2; i<=n; i++) {
        if(!notp[i]) p[++p[0]] = i, varphi[i] = i-1;
        for(int j=1; j<=p[0] && i*p[j]<=n; j++) {
            notp[i*p[j]] = 1;
            if(i%p[j] == 0) {varphi[i*p[j]] = varphi[i]*p[j]; break;}
            varphi[i*p[j]] = varphi[i]*(p[j]-1);
        }
    }
    for(int i=1; i<=n; i++) varphi[i] += varphi[i-1];
}
ll cal(int n, int m) {
    ll ans=0; int r;
    for(int i=1; i<=n; i=r+1) {
        r = min(n/(n/i), m/(m/i));
        ans += (varphi[r] - varphi[i-1]) * (n/i) * (m/i);
    }
    return ans;
}





（ 转载）

离散数学

容斥原理

定理

实质

错排

总结

莫比乌斯反演 Mobius Inversion

说明

积性函数

定义

狄利克雷卷积

计算

莫比乌斯反演

应用

栗子

代码

相关

关于离散数学到了期末这件事

标签