高维前缀和

问题的引入

一个\(n \times m\)二维矩阵\(A\)的前缀和\(S\),一般来说定义为\(S_{x,y}=\sum_{i=1}^{x}\sum_{j=1}^{y}A_{i,j}\)。

代码常见的写法就是用容斥加加减减:

这是二维的情况,如果是三维或者是更高的k维,不难发现复杂度有一个\(2^k\),指数爆炸了。

然而,用高维前缀和的技巧,就可以有效的将时间复杂度降下来。具体的思路是一维一维的求和。比如还是刚才二维的例子,为方便叙述,想象矩阵左上角是\((1,1)\),我们先对每行分别从左到右累加,即对每行求一维前缀和,再对每列从上到下累加,还是相同的过程,这样求出的结果就是二维前缀和了。也可以从定义前缀和的式子入手考虑,每个求和号就代表一个维度,我们的计算过程就相当于一个求和号一个求和号的算,比较简单。

高维前缀和代码,简洁的一匹:

子集和变换

高维前缀和在二进制数上的应用就是做子集和变换。比如有一些小于\(2^{20}\)正整数给一个数x,我要统计所有满足\(x\&y=y\)的数y有多少个,这里的and就是二进制与。这里其实还是高维前缀和,可以把每一个数看成20维超立方体的其中一个格子,满足上述式子的x和y的关系就是,每一个维度下y对应的值都要小于等于x对应的值(虽然每个维度只有两种值,0或1)这样就是相同的问题了,于是我们不仅可以维护一个子集的信息,还可以维护超集的信息,维护的内容也不只限于求和,还可以求最值等等。

求超集和:

第一层循环枚举维度,第二层枚举所有元素,注意第二层循环正序或者倒序都是一样的,因为每个维度大小只有2,即0或1,做的就是把“1”加到“0”上。

练习题目

1.SPOJ Time Limit Exceeded

简单的递推一下就是记\(dp_{i,j}\)表示考虑前i个数,第i个数为j的方案数,转移方程很容易\(dp_{i,j}=\sum_{k=0}^{2^m-1}dp_{i-1,k}[j\&k=0]\),并且如果j是\(c_i\)的倍数,那么\(dp_{i,j}=0\)。

然而朴素的转移是\(O(n(2^m)^2)\),显然会TLE。转化一下\(j\&k=0\)等价于\(j\&(~k)=(~k)\),那么我们把上一次的dp值状态取反,然后求超集和就ok了,时间复杂度\(O(n^{2}2^{m})\)。

2.codeforces 449D – Jzzhu and Numbers

求and起来为0的子集的个数。

先用高维前缀和算出\(dp_S\)表示状态包含S的数的个数,然后令\(2^{dp_S}-1\)就是and起来包含S的子集的个数,然后再高维差分回去,就能求出答案了。

3.hihocoder 1496 寻找最大值

求\(a_i\times a_j \times (a_i \& a_j)\)的最大值,枚举&值,前面就选超集中的最大值和次大值,用高维前缀和处理出来。

4.2016 Multi-University Training Contest 4 Bonds

给一个不超过20个点的无向连通图,无重边无自环,求每条边被多少个极小割边集包括。

显然能观察到极小割只会将图分成两个连通块,那么我们先用点的连通性作为状态bfs一下,得到所有可能的分法。之后如果暴力统计的话复杂度就是\(O(n^{2}2^{n})\),我们计算反面,每条边极小割边集出出现的次数等于极小割总数减去这条边连接的两点在同一连通块的情况,然后就可以高维前缀和了,\(O(n2^{n})\)。

5.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest F.GCD

先从n个数中随机一个数,然后就有大于二分之一的概率选到了最优解中的一个数,那么枚举这个数的所有约数,用至少是n-k个数的约数的数更新答案,重复多做几次,降低随不到的概率。关键是怎么不暴力的做后面说的这个事情。首先,一个\(10^{18}\)范围内的数的约数个数不会很多,大概几倍的\(10^{6}\)就够,这个可以等完写个搜索验证一下。然后将随到数分解质因数,每个不同的质因数看成一个维度,然后求个高维后缀和,就可以了。