反演

假设有两个函数和满足:,已知f求g的过程称为反演.

一般情况下,求反演只能高斯消元,但是有一些形式的反演有巧妙解法.

子集反演

一般形式:

证明:

不难发现,这个子集反演也就相当于在做高维前后缀和.

Example1(2019zrpzt七连day1D)

根据子集反演,设为集合为的数量,然后设,有:.

做一遍高维前缀和就好,复杂度,应该也可以用分治FMT无脑做到.

Example2(有标号DAG计数)

设表示个点,其中有个点的入度数为的方案数.(等一下,为撒子想到要记度数为的点咧?因为你要一层一层转移,而在DAG中一层一层的就是零度点.而且说到底,你注意到有编号这个事实其实是很烦的,因为考虑如果一个一个点放上去,就有可能出现放的地方是等价的.而这么一层一层是绝对不会出现等价点的问题的.再说的仔细一点,如果我们把位置空着,然后选出一些放上来,是会出现等价点的问题的.但如果我们先选出来,然后再把边连上就不会.于是我们必须要枚举一些点然后再连到上面去)

这样我们每次枚举删去这个点后,还剩下个零度点.于是自然有:

等一下咧,这复杂度了,这咋办啊?

好像转移优化不太了,因为很难省去(在指数上).但我们注意到我们定义的时候说:度点的数量恰好为,这个条件好像太强了果然OI就是发现限制太强了就弱一点,发现太弱了就强一点,所以我们想办法把它放弱一点.

一个经典的方法是:我们把定义改为至少个零度点.但是这样转移好像还是不太行:零度点的情况太多了.那我们不妨考虑容斥,因为推导容斥的过程中,永远不害怕情况太多:我们直接考虑所有情况的集合.当然能不能推到最后是另一回事.

我们设表示个点,其中只有中的点的入度为;类似定义表示个点,至少中的点的入度为.显然我们所求也就是,注意到:

对第二个式子用子集反演,有:

接下来使用反复带入大法:

可以发现:我们在推式子的过程中,将和集合本身有关的性质转化为了只和集合大小有关的式子,于是就简化了大量运算.

接下来我们继续化简:

注意到复杂度已经降到了.

上面是从集合的角度一步步分析得到的.但如果你直接从容斥的角度考虑,忽略掉那个,把它当成一个可以数学归纳出来的容斥系数,那么这个式子会得到一个很简单的理解方式:

也就是直接设,然后钦定其有至少个,然后配容斥系数.

二项式反演

一般形式:

显然以代替即可从第一个式子推导第二个式子,下面证明第一个式子:

Example1(错排问题)

个有编号的人站成一排,求他们都没有站到自己编号对应位置的方案数.

设为个人随便站的方案数,为个人都站错的方案数.

如果知道的表达式,我们可以通过枚举有多少人站错位置来得到,即:.

显然就是一个二项式反演,.

值得一提的是,我们再观察一下最后得到的错排公式并进行一定的化简,可以得到:.

不难发现的后面形如的泰勒展开,我们考虑直接将泰勒展开的公式带入,可以得到:

用一些我不会的方法分析误差,会发现后面的项所能带来的误差很小,于是有.

另外,观察关于的表达式,不难求出的递推式:.

下面证明,事实上,右边等于:

Example2(CF1750G)

如果没有字典序限制就是经典的二项式反演:考虑能被分为段,说明有个位置和前一个位置是大一的关系.我们钦定这些位置即可.

而有字典序限制也很经典,枚举LCP,枚举下一个位置,这个时候值域被分为若干个区间,假设剩了个数字,个区间,那么钦定对的方案是.然后要乘上前面已经有了的,也就是乘上形如.这样复杂度.

这种问题通常LCP后的下一个位置都可以规避,这里你发现不同的取值只会让后面的有种不同的取值,因此不用枚举.这样就是.但是那个多项式乘法也可以规避,考虑最后的答案形如,我们考虑写成,然后不断这么做,就只需要.

Example3(CF1228E)

不妨设至多有行列最小值为的答案是,恰好有行列最小值为的答案是,注意到:

令,则,而.做两次二项式反演得到.

写到这里发现一个问题(其实是我发现问题后把上面原本写错的给改了),为啥呢?我们写成子集反演形式看看:

做子集反演:

把集合改成集合大小就可以发现问题所在:

换句话说,本身就包含了所有的情况的和,并且在组合数那里就找到了唯一确定的,因此是唯一确定的.这意味着这里的并非集合之和,而是已经确定的集合的大小.

啥?这和我平常接触的二项式反演不一样啊?不说别的,第四题(BZOJ2839)的式子是这样的:

冷静一下,二项式反演的公式肯定没错,那也就一定是下面这几句出现了问题:

这个问题其实非常显然,我们的定义为所有的答案之和.也是这么定义的,那这个式子就是错的,应该写成:

这样才是在不确定的那些行列中选择组合数,而不是在确定的那些行列中选.

但这样又有一个问题,就是这个题的特殊性,这个题要求,那此时怎么定义不应该是一样的吗?

当然不一样,二项式反演讲究统一性,所有的定义必须遵循一个统一的原则,不然如果什么样子的函数都能反演,那一般的反演就不是一个需要解方程才能完成的东西了.

回到第四题,再看一遍这个式子:

这个定义式就非常良性,是已知的集合,是未知的集合.我们乘上组合数就可以得到对于来说已知的集合.因此这个就非常正确.

回到这个题上,为什么我们最后把的定义改成就对了呢?

再看看这个式子:

这个式子的右边在干这样一件事:那就是在已知行列的集合的前提下,从中选出行列并求.那么你从哪知道的行列呢?你得组合数啊!

所以,实际上的是这样的:

好麻烦啊,能不能避免这种需要进一步思考集合意义的问题呢?

考虑二项式反演的第二个形式:

不难发现这个式子无论怎么写,前后都一定是从已知集合中选东西.绝对不会出现上面的问题.

因此,我们重新写一下这个题的相关式子,考虑直接正难则反,设为至少有行列不满足条件的方案数,自然有.你发现此时一定有:

最后答案就是.

斯特林反演

一般形式:

考虑第一类斯特林数和第二类斯特林数的对称性,只需证明第一个和第三个式子即可.

反转公式:

第一个式子的证明:

第三个式子的证明:

莫比乌斯反演

一般形式:

第一个式子的证明:

注意到.

第二个式子的证明:

第三个式子的证明:

Example1

求长度为且仅包含小写英文字母且循环节长度恰为的字符串个数.

不妨设表示长度为的字符串个数,表示长度为且循环节长度恰为的字符串个数.

有,根据莫比乌斯反演,.

Example2

求.

我们通过这个题来讲一下推导技巧.

增加枚举量

交换枚举顺序

分离无关变量

考虑使用数论分块,只需处理出的前缀和即可在的复杂度解决此问题.

Example3

求.

和上一道题几乎没区别,唯一不同的是需要处理的函数从变为了.

Example4

求.

考虑增加枚举量,则:

于是转化为上一道题,但复杂度仍不可接受.

换元

考虑设,则变为.

Example5([UR #5]怎样跑得更快)

首先先考虑去掉使得式子中只有.

显然可以构造函数,然后将题目转化为.

很难处理,于是考虑用莫比乌斯反演消掉.

可以求出使得,也即.

则原式即:

令,有.

这个也是一个莫比乌斯反演的形式,我们可以求出左边,进而求出.

而,可以再次使用莫比乌斯反演求出,进而求.

无解条件显然是.

简而言之,这个题的步骤就是:

  1. 通过增加枚举量消掉以及这些难以处理的项.

  2. 将与尽量分到式子两边.

  3. 先通过莫比乌斯反演求出一些值,再通过这些值反推.

Example6([CF1566H]Xor-quiz)

首先注意到一个重要的事实:我们只需要询问所有的,就可以得到全部信息,而这些的数量是完全足够我们全部询问一遍的.

注意到一个事实是,异或是模意义下的按位加减法,这意味着我们可以对异或做莫比乌斯反演.事实上,我们有:

注意到,于是:

接下来只要我们形式上写作,我们就默认,又令,此时自然有.这是一个经典的莫反形式,我们再反演回去就可以得到,也就是说我们可以求得所有的,也就是这个集合中所有是的倍数的异或值.

注意一个事实:如果我们设,那么我们就可以按照的不同将所有数划分为若干个集合,每个集合在每次查询的时候要么都不被异或要么都被异或.这也告诉我们:我们只能求出每个集合中被选进的这些数的异或值,而不能分开得知它们.接下来考虑如何知道这个,不妨设,又设.考虑用表示,我们有:

反演,有.于是我们可以求得所有的了.

现在的问题在于:对于数,我们要在中选出若干个数,使得它们的异或和为,并且选出的数字总共有个.

然后是根据数据随机,拿每个集合的线性基随机一下自由元,然后对着构造.多随机几次,最后做背包.

多重子集反演

设为可重集合.

一般形式:定义,若包含重复元素则为,否则为.

证明:

根据莫比乌斯反演,这个是显然的.

单位根反演(离散傅里叶变换)

一般形式():

可以发现这个式子其实就是FFT时所做的DFT与IDFT.

一般情况

考虑莫比乌斯反演的过程,我们实际上使用的是.

令,左边.

令,,那我们有.

刚才的过程相当于:

无论是二项式反演还是莫比乌斯反演,他们都满足所依赖的有.

根据上面的情况,我们发现是一个下三角矩阵,是.

现在来推导满足的一般情况反演:

不妨设算子,满足.

即.

由上我们发现,反演解决了一些在下标上的二元运算卷积:

而我们需要把分成两个独立的部分,通常正变换一下,处理一下,逆变换回来.

容斥

一般形式

即:将求并集中元素个数转化成了求交集中元素个数.

我们有:.

证明:我们考虑对于每个元素,看它对最终答案的贡献.假设它所属个集合,而除了这些集合以外的集合,

显然,当这个元素被包含的时候,贡献为,反之贡献为.

如果我们定义一类在集合上的函数,那么自然也有:

另外,我们上面的做法是:当交集好求时求并集.我们还可以使用一步补集转化:

这样我们同样可以在并集好求的时候求交集.

会发现容斥和二项式反演是很像的.但是不一样的是,容斥是从集合的角度考虑,更注重单个元素的贡献;二项式反演是从函数的角度考虑,更关注函数之间的转化.

Example1(不定方程非负整数解计数)

考虑不定方程,和个限制条件,其中和都是非负整数,求该方程的非负整数解的数目.

首先,我们需要找出全集,以及刻画中元素的(条件):

  1. 是满足的所有非负整数解;

  2. 对于每个变量,都对应一个.

设所有满足的解构成集合,那么我们需要求解的值就是.而显然是.我们有:.考虑对使用容斥原理,注意到的意义是满足的解的数目.换句话说也就是部分变量有下界限制,那直接左右两边同时减去下界即可.于是枚举子集即可实现.

欸,等一下,咋想到的补集转化,又是咋想到要用容斥的捏?

我们冷静一下,首先补集转化和容斥都是一个思想:正难则反.我们要求满足条件的个数,就先想一下能不能求不满足条件的个数,然后拿总的个数减去.然后注意到不满足条件的意义是:有至少一个不满足,这样就很可以容斥了.

Example2(错排问题)

我们考虑从容斥的角度再次认识一下错排.

首先,我们需要找出全集,以及刻画中元素的(条件):

  1. 是长度为的所有排列;

  2. 对于每个变量,都对应一个.

注意到所求仍然是.于是我们仍然试图.考虑其意义,也即:有个位置被确定了,而其它位置没有限制,于是.根据容斥,自然有:.

Example3(bzoj3622已经没有什么好害怕的了)

首先可以用dp+双指针得到表示勒令对满足条件的方案数.把的定义改为恰好对满足条件的显然是同强度的.

我们接下来仍然考虑容斥,首先,我们需要找出全集,以及刻画中元素的(条件).

等一下,这个好像不好刻画?

我们先回归一下容斥的本质:考虑每个元素的贡献.注意到恰好对的方案会被钦定对的方案计算次.我们再考虑一种方式理解容斥:我们一步一步把正确的答案消出来:简单来说,我第一步让所有恰好为的方案贡献为,其它的可能也有贡献,但我们忽略他们.第二步让所有恰好为的方案贡献为,第三步以此类推.于是这个题,我们考虑也这么做:这样第一步令,第二步除去其中被多算的,这一步令.这个时候,我们再考虑的贡献:它将在时贡献次,在时贡献次,那它现在的贡献还有:次.以此类推,可以得到.

等一下,这也太麻烦了,就不能从集合的角度分析嘛?

冷静一下,如果我们要做容斥,我们必须考虑每个元素单独的贡献,但是在这个题中,每个元素并没有单独的贡献,而是整个集合需要满足性质才能贡献.也就是说,我们无法分析每个.而考虑集合就需要将集合分类,从而使用二项式反演.

换句话说,这个定义在集合上的函数并不满足可加性.

换句话说,我们要用容斥,就一定要刻画,因为只有这个时候,我们才能通过分析满不满足的解集的交并来实现.

再换句话说,大部分的所谓的容斥其实都和集合没啥关系,我们做容斥就是需要逐个考虑贡献,把它们贡献全都杀成就行.

Example4(HAOI2008硬币购物)

如果直接对于每次询问暴力做,复杂度显然是,无法接受.于是考虑预处理来降低单词询问复杂度.

注意到硬币数量很少,并且每个硬币的贡献可以独立计算.我们完全可以刻画,从而可以用容斥做.复杂度.

Example5

Alice和Bob在玩游戏,他们有一个个点的无向完全图,设所有的边组成了集合,他们想取遍的所有非空子集,对某个集合有一个估价:考虑个点与中的边组成的图,我们用种颜色对所有点染色,其中同一个连通块的点必须染成一种颜色,那么等于这个图的染色方案数.同时,Alice喜欢奇数,所以当为奇数时,Alice的分值加上,否则Alice的分值减去,求最后的分值..

一开始抄题的时候没有写染色而是直接写"设为连通块个数,则."然后发现做不了,因为相同的不尽相同,而且可能情况还蛮多的.冷静一下,注意到连通块这个性质太强了:如果我们把它放到指数上,那应该会做得很痛苦.所以我们考虑每有一个连通块就乘上一个,这个看上去就简单一些.

但是这样好像还是不太好做,毕竟现在我们面对的还是一个难以转化为计数问题的图论问题,只是把问题的单位元素从图变成了连通块.那我们能不能再进一步:把单位元素换成单点呢?

考虑由于连通块要染一种颜色,那.注意到这是一个单位元素更小的限制条件!并且我们发现我们将与有关的单位元素(从一开始就是点)和与有关的单位元素统一起来了.这也提示我们做计数的时候,尤其是做容斥的计数的时候,最好先将单位元统一,这样后面才可能更容易做.

接下来就可以写式子了,令表示在情况下的染色方案,表示满足边限制的解集:

冷静一下!这个东西和容斥长得那叫一个一模一样啊.我们看看能不能逆向分析出的意义:显然是.也就是完全图中至少有两个点颜色相同的染色数.根据补集转化,我们只需求出两两点不相同的染色数即可.所以最后的答案就是.

Example6

求.

考虑这么一个事实:假设,注意到令,我们所求也就是.于是可以用上面的方法做.另外,这里的做法引出莫比乌斯反演.

Example7(AGC058D)

直接容斥好像不太可做,我们把容斥中的条件改为有多少个极长的形如这样的串.

乍一看这个极长的条件好像巨难满足,但实际上我们冷静一下,我们只需要满足这个串长度大于等于并且开头不能往前延申就可以了,后面其实是没啥必要管的.

拿组合数算一算.

Example8(AGC035F)

显然问题只在于重复计算的问题.我们先将所有状态做一个双射:对于一个网格,唯一可能被重复计算的只可能是一个拐角的,我们让这种情况下的行尽可能长.

然后捏?注意到这样的话一个拐角的角一定是行了,是列就一定不合法,我们考虑把不合法的列杀了.

于是做一下容斥,答案是.

Example9

给定若干个限制条件,表示和必须满足至少一个,求排列方案数.

首先把排列转化成图,这样上面的限制条件也就是有一些无向的链和环,最后定向.一开始以为随便做做,思考一下注意到如果有长度为的链,它自己成环的话是不用的.

这咋办.一个办法是:我们考虑容斥,先随便放进去,最后再钦定若干个自己成环.诶等一下为啥这个容斥是对的?因为系数是,所以一个有个单独成环的状态会被随便放的情况恰好多算一次.类似可以做容斥.

当然,也可以考虑先把其它的合并,最后做长度为的链,但是!一开始一定要钦定有序,最后再用组合数统一算答案.因为一开始带着顺序做很难做.

Example10([AGC036F] Square Constraints)

由题意得:.

当一个东西有上界又有下界的时候可以想到容斥.问题转化为只有上界.假设最后所有的上界为,那么只有上界的答案应该是什么呢?将从小到大排序,答案就是.(注意到必须满足.)

但是这个东西和容斥怎么结合起来呢?我们将限制放到二维平面上,注意到上下界的限制其实是两个的圆弧.而通过圆弧的性质不难看出:最终的分为三部分:在下半部分圆弧上的,在上半部分圆弧后面的,在上半部分圆弧前面的.而如果想知道按照顺序排序,我们只需要对前两部分做归并,然后将最后一部分直接放到后面即可.于是我们考虑按照的大小为顺序进行一个类似归并的东西,每次判断当前下半部分圆弧是否要往上加点即可.这样我们可以处理前两部分对答案的贡献,但问题在于第三部分对答案的贡献怎么做,我们需要找到第三部分上的点在排序后的位置.我们预先枚举容斥集合的大小即可,这样就可以快速算出这个东西,于是复杂度.

Example11([23省选第一轮集训day4]C带劲的旅行)

(下面将和反着写)

设.

首先注意到期望.

考虑如何计算,如果我们设表示以作为开头的极长的带劲的长度大于等于的序列的集合,那么最后无非是要求所有的并.考虑用容斥做到求所有的交.不过要注意讨论一下是不是第一个点.

Example12

给定和个点各自的颜色,对有编号无根树计数,要求相同颜色组成的连通块大小不超过..

著名结论:个点个连通块任意连边成树的方案数是,其中是每个连通块的大小.但是,如果我们强行对每种颜色分成若干连通块,我们要防止它们之间有边.这就是我一开始没做出来的原因:要容斥的根本不是树的大小不能超过,由于树的形态多变,这个是不能维护的!正确的做法是找到若干个相同颜色的大小小于等于的连通块,要求它们两两无边.甚至根本就不是它们可以连边但是大小不能超过,我们要容斥的东西一定要好算,简单.

然后就做完了,每次暴力合并若干个颜色相同的块,容斥系数块数.

容斥是一个层层递进的东西,我们每一步都是基于上一步的限制:它本身就是一个求解集的东西.

Min-Max容斥

对于:

考虑一个特例:,那么上面的式子导出min-max容斥(我们设)(第二个式子可以把前缀改成后缀):

由于是集合,这个式子在期望意义下同样成立:

进一步,这个式子可不止能求min-max的转化,它可以求出集合中第k大的数字:

原理是消掉前大的数字,让他们的贡献为,剩下的配一下容斥系数.

Example1([23省选10连测 day6]A)

不妨设为第一次被覆盖的时间,答案就是:

设为有多少个区间能覆盖至少一个,考虑,于是.

于是:

注意到可能不那么好求,我们求,也就是不包含任何一个的区间个数,我们有:

这里已经不难写出的dp了.

那么怎么优化呢?设表示只考虑时(必选),的答案,不难发现每次加入一个区间就会让对的贡献乘一个.

如何处理这个事情?我们用类似多项式的东西,前者相当于平移多项式系数,后者相当于标量乘法,然后拿线段树维护和,复杂度.

反射容斥

一般形式:给定二维平面上两个点和,其中在的右方,给定两条线和,每次可以向右上或者右下走一步,求不碰线的从到的方案数.

我们不妨设表示一定碰了一次上界的方案数,表示一定碰了一次下界的方案数,表示一定碰了一次上界后碰了一次下界的方案数......

最后的答案就是随便走.

考虑设步数为,那显然长度最多为.