竞赛讨论区 > 【博客】反演学习笔记(含非卷积证明法详细证明)
头像
洁骜攻子
发布于 2019-04-09 20:51
+ 关注

【博客】反演学习笔记(含非卷积证明法详细证明)

什么是反演:

有函数F(x),令,其中x与s的关系自定,在已知GF的过程叫反演。

集合反演:

公式:

推导过程: 核心是容斥。

1.首先,当那么所有都被加入,我们要把除了x之外的都删掉。

2.我们将xs相差1的都减去,他们两两之间的交***减两次,还要再加回,那么就变成了容斥的形式。

莫比乌斯反演:

公式:

推导过程:与集合反演类似,但是更加复杂,核心也是容斥。

首先,代表G(x)要加入还是删除,类似于集合反演,我们想要找到在dn的某种关系下固定的系数,对于集合是,对于莫比乌斯反演,我们选择。我们令,分类讨论:

,即,我们必须选,于是

t是质数,是n变成“子集”的最小单位,我们把他删除,

t是两个不同质数的乘积,那么d被这两个质数删了两次要加回,那么

那么三个质数时呢 ,我们又要减去,现在又变成了容斥的形式,所以当tk个不同质数的乘积时

我们发现整个过程已经完毕,那么其余

总结-莫比乌斯函数:

一些公式:

(组合数可证)

(左面通分,同去掉分母n,根据反演可得)

(反演回去可得

扩展-莫比乌斯反演的另一种形式(更加常用):


与原式一样容斥可得到。

应用:

f(x)的数对个数,g(x)的数对个数,那么:

根据扩展:

于是

全部评论

(4) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐