首页 > 其他分享 >反演

反演

时间:2023-01-16 10:45:52浏览次数:38  
标签:系数 函数 容斥 反演 文氏图 二项式

本人刚学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

相关文章

  • 莫比乌斯反演学习笔记
    莫比乌斯函数定义\[\mu(n)=\begin{cases}1&n=1\\0&n\text{含有平方因子}\\(-1)^k&\text{其中}k\text{为}n\text{本质不同的质因子个数}\end{cases}......
  • 莫比乌斯反演
    莫比乌斯反演考虑狄利克雷前缀和的式子,\(g(n)=\sum\limits_{d\midn}f(d)\)。知\(f\)求\(g\)是naive的;知\(g\)求\(f\)呢?首先上式等价于\(g=f\astI\)......
  • P3704 [SDOI2017]数字表格——莫比乌斯反演
    莫比乌斯反演\(\color{red}{f(n)=\sum\limits_{d|n}}g(d)\Leftrightarrowg(n)=\sum\limits_{d|n}\mu(d)f(\dfrac{n}{d})\)例题:P3704[SDOI2017]数字表格题意:给出\(n,......
  • 狄利克雷卷积和莫比乌斯反演初探(施工中)
    0.前置知识瞅这1.狄利克雷卷积定义定义域为\(\mathbb{N_+}\)的函数称为数论函数。对于两个数论函数\(f,g\),其狄利克雷卷积为\(h(n)=\sum\limits_{d\midn}f(d)......
  • 莫比乌斯反演草稿纸
    这只小蒟蒻做莫比乌斯反演的练习题时用$\LaTeX$打了一些草稿,又不舍得扔掉,于是放在这个博客里供大家欣(tu)赏(cao)。P2257YY的GCD$$\text{求}\sum_{x=1}^n\sum_{y=1}^m[g......
  • HDU 6439 2018CCPC网络赛 Congruence equationI(杜教筛 + 莫比乌斯反演 + 伯努利数)
      大致题意:给你一个长度为k的序列a。对于序列c,当  时,;当时,取[0,m)中任意一个数字。令  表示满足  的序列c的方案数。现在让你求 。          ......
  • 莫比乌斯反演
    莫比乌斯函数 设正整数$x=p_1^{c_1}p_2^{c_2}...p_m^{c_m}$,定义函数 $\left(\begin{array}{ccc}1&2&3\\4&5&6\\7&8&9\\0&0&0\end{array}\right)$......
  • 拉格朗日反演学习记录
    \(\texttt{updating……}\)多项式复合对于多项式\(F(x),G(x)\),其复合为:\(F(G(x))=\sum_{i}[x^i]F(x)G(x)^i\)求法:设\(B=\sqrtn\)\[\begin{aligned}\sum_{i=0}^n[x......
  • 杂谈:二项式反演与多步容斥
    这是两个本质不同的东西。多步容斥是“至少或至多选若干个”到“恰好选若干个”的变换。而二项式反演是“钦定选若干个”到“恰好选若干个”的变换。二项式反演虽然形式上......
  • 一种关于子集异或和的冷门反演
    前言本文用集合的符号表示二进制数。具体地,定义全集\(u\)是\(2^n-1\),某个二进制数\(x\)第\(t\)位是1可以理解为为\(x\)中有\(t\)号元素,否则没有。定义\(|x|......