本人刚学OI一秒,对了解众多反演之后对反演的本质有一些看法
本人现阶段学过的反演和类似反演的包括:容斥,二项式反演,莫比乌斯反演,子集和反演。Min-Max容斥单位根反演斯特林反演等等还没有掌握,内容一定可能会以偏概全
本人大致观测了一个美妙的普遍规律:
反演就是普通容斥在高维空间的推广,容斥系数都可以通过文氏图得到
一个有一个或多个维度坐标的函数(或者说多元函数)$ f $,在每个维度上以某种一定的规则叠加为函数 $ g $,我们把 $ g $ 通过容斥系数拼凑出函数$ f $,就是反演的过程
比如莫比乌斯反演中,叠加的规则就是因数与倍数,在有的容斥或反演中,可能就是前后缀
那么容斥系数(这里只包括 $ 1,-1 $ )是什么,先给出我的看法:
我们认为一个 $ n $ 元函数的参数就是它在 $ n $ 元空间里的坐标,那么假如我们要用 $ g $ 反演出 $ f $,容斥系数取决于每一个 $ g $ 与所求的 $ f $在多元空间里的曼哈顿距离的奇偶(比如奇 $ -1 $ 偶 $ 1 $ )
可以联想到莫比乌斯函数和多维二项式反演
我感觉我说到这反演做多的dalao就能明白我什么意思了
至于为什么:文氏图
将文氏图推广到多维空间,就得到了多维容斥的系数,或者说反演只是容斥在更高维度上的推广
所以不同反演是可以互通并且快速掌握的,比如我们可以把集合大小为 $ 2^n $ 的子集和反演类比于 $ n $ 维的二项式反演
笔者的语言表达能力只能到这,望dalao们分享看法
标签:系数,函数,容斥,反演,文氏图,二项式 From: https://www.cnblogs.com/Sakura-Lu/p/17054852.html