Min-Max容斥

Min-Max容斥,也叫最值反演(脑子不够,套路来凑),可以处理一些计数问题。

形式(公式挂光了,救救孩子):

Max(S) = \sum_{T \subseteq S} (-1)^(|T| + 1) Min(T)

Min(S) = \sum_{T \subseteq S} (-1)^(|T| + 1) Max(T)

 

本质上是容斥TAT,用反演的角度来看,就是只有当T的size为1且是最大值时才会被计入贡献(等式咕了

这里的Min与Max并一定要是最大值和最小值,只要是在某一种偏序下的两个极端就好了。

基本上的套路大概就是随机选一段子集染色,问期望多久把全集染满——这是Max,就可以转化成对于每一个子集,期望第一次被染色的时间的值——这是Min。

 

好像还有GCD和LCM的转化,待填。

莫比乌斯反演

本来还打算写容斥的,结果不知不觉就过(颓)了好几个月,发现原来容斥如此高妙啊QAQ,那就讲讲比较套路的反演吧。。。

莫比乌斯反演。。。听起来很高明,实际上不算太难吧(逃

首先说他是莫比乌斯反演,总要有个缘由吧。个人感觉就是因为莫比乌斯函数,μ,是他的精髓所在。

先说说μ的定义

  • n为无平方因子数且n的标准分解中有偶数个质数,μ(n) = 1;
  • n为无平方因子数且n的标准分解中有奇数个质数,μ(n) = -1;
  • n为有平方因子数时,μ(n) = 0。

 

  • μ(n) = 1 if n is a square-free positive integer with an even number of prime factors.
  • μ(n) = −1 if n is a square-free positive integer with an odd number of prime factors.
  • μ(n) = 0 if n has a squared prime factor.

source: Wikipedia(En)

看到这个定义,大家想必会非常奇怪——这种sb的定义是谁想出来的,一点也不优美!

但是,大家且和我看看别处:

狄利克雷卷积

(不得不吐槽,wordpress真的好菜菜啊,不能用LaTeX,只能靠截图,不然这篇博客好打多了)

又是定义

TIM截图20180712174346.png

其中,fg为数论函数(定义域为R,值域为C的函数),* 代表的就是狄利克雷卷积。

不难看出,在狄利克雷卷积的意义下,单位元为函数:TIM截图20180712175524.png

另参见:Dirichlet convolution

看到单位元,很自然的便想到逆元。在乘法意义下,最特殊的数莫过于是1了,它的乘法逆元就是它本身。那我们合不考虑在狄利克雷卷积的意义下 1 函数(函数值恒为1)的逆元呢?

不难猜出发现这个函数就是莫比乌斯函数

证明过程(太懒了,不想打公式了233)

那这个性质就可以写成一个求和(卷积)的形式

TIM截图20180713193453

这个性质在推式子的时候非常有用。

 

有了以上知识,莫比乌斯反演就呼之欲出了。

 

莫比乌斯反演

和大多数反演(反演好多啊。。。以后应该还会专门写这样的博客吧好一个flag)一样,莫比乌斯反演就是在一种卷积的意义下通过已知量关于未知量的表达式来求得未知量的方法。

考虑以下问题:

已知 ,且 f * 1 = g ,

我们可以先回忆一下当这种卷积是各个情况时,我们会怎么做:

  1. 加法,如 x+3=5 我们通常在等式两边同时减去3
  2. 乘法,如 3×x=6 我们通常在等式两边同时除以3
  3. 模意义乘法,如 3×x=1(mod 2) 我们通常在等式两边同时乘以1
  4. ……

看到这儿,大概也就有了眉目:在一种卷积意义下,只要在等式的两边同时卷上该卷积意义下与x做卷积的数的逆元,就可以得到答案辣!

那么,我们是不是只要在等式两边同时卷上μ就稳了啊?

TIM截图20180713204316.png

这就是传说中的莫比乌斯反演了啊。。。是不是很好理解啊233

 

那么这篇博客就先到这里了啊,还有一些技巧一类的东西就以后在写题目题解的时候写吧!

 

顺便,之后更新的时候会把自己之前做给同学上课用的ppt发上来啊,敬请期待吧

(感慨一句,一万年之后终于写了博客了啊啊啊)

康托展开

之前对于“XX展开”一直都非常忌惮(想必是初一看泰勒展开的时候被吓傻啦),然后前几天讲搜索的时候提到了康托展开,我一查wiki(这个链接是中文界面维基百科的,然而我又没有找到对应的英文界面,所以要进行一波骚(fan)操(qiang)作)才发现——

就是个编码嘛!

公式如下:

{\displaystyle X=a_{n}(n-1)!+a_{n-1}(n-2)!+\cdots +a_{1}\cdot 0!}

这就是全排列进行编码,原来要10ⁿ存的数据,现在n!就可以做到!

解释一下上述公式的含义:ai表示在当前这个排列中比i这一位数字小的个数(第一个数字为第n位,以此类推)

举个栗子,

例如,3 5 7 4 1 2 9 6 8 展开为 98884。因为X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.

解释:

排列的第一位是3,比3小的数有两个,以这样的数开始的排列有8!个,因此第一项为2*8!

排列的第二位是5,比5小的数有1、2、3、4,由于3已经出现,因此共有3个比5小的数,这样的排列有7!个,因此第二项为3*7!

以此类推,直至0*0!

那么这样,就可以轻松的编码了。

 

继续阅读“康托展开”