高维前缀和略解

Ameiyo · 2019-05-12 13:24:04 · 个人记录

高维前缀和略解

前言

似乎我们教练也说是叫 高维前缀和 。。。

那么高位前缀和又是什么呢。。。

算了这些是题外话。

关于高维前缀和：

目前看来可以用于 DP 的优化，但是有一定的局限性。

若对于所有的状态 S ，其需要向 S' 贡献答案，在这里我们称 S' 为 S 的父亲， S 为 S' 的子孙。

高维前缀和的使用条件:

(这个条件其实无视也无所谓，因为是我自己根据证明方法胡诌的。换句话说，如果证明方法，或者说更新方法不一样，约束也就不一样了)

(1) S' 的父亲必是其子孙 S 的父亲之一。

(2) S 到其某个父亲的 S' 的转移路径或是直接转移，或是能通过其他直接转移一个个转移上去，并且中间的状态必是 S 的父亲。

(3) 父子关系不能有环。

从上述第三点也可以看出状态的转移满足无后效性，所以高维前缀和往往是对 DP 的优化。

loop d : // 遍历所有直接转移
    loop S : // 遍历所有状态
        if (check(S + d)) dp(S + d) += dp(S) // 如果合法，更新

而 DP 的做法往往是这样:

loop S : // 遍历所有的状态
    loop D : // 遍历所有转移，包括间接转移
        if (check(S + d)) dp(S + d) += val(S) // 如果合法，更新

这个代码看起来没有 DP 的样子，实际上他可能是某个 DP 的内层，这个时候优化可能就很有用了。

对比两份代码，我们会发现高位前缀和对时间的优化主要是针对转移。相当于是把大的转移拆分成小的互不干扰的转移，这种优化实际上有一个很经典的实例—— 多重背包的二进制优化 。

在理解时，可以借助二进制优化来思考。

更详细的讲解

为了更好的理解，这里先使用较常用的二进制表示集合(状态)的方法来做例子。(没错就是刷状压时遇到的QAQ)

先看一道题。

CodeChef MAXOR: Good Pairs

(这里给出的是 vjudge 链接)

You are given N integers: A_1 , A_2 , ..., A_N . You need to count the number of pairs of indices (i, j) such that 1 \leq i < j \leq N and A_i | A_j \leq max(A_i, A_j) .

给你 n 个数，每个数是 A_i ,求有多少对 (i, j) ，满足 A_i | A_j \leq max(A_i, A_j) 。

1 \leq N \leq 10 ^ 6 0 \leq A_i \leq 10 ^ 6 1 \leq Sum\ of\ N\ over\ all\ test\ cases \leq 10 ^ 6

因为 x\ |\ y\ \geq x ，所以满足 A_i\ |\ A_j \leq max( A_i,\ A_j ) 就相当于 A_i\ |\ A_j\ =\ max(A_i,\ A_j ) 。在 A_i \leq A_j 的时候就相当于 A[i] 的二进制表示法是 A_j 的子集(被包含)。

我们用 f[i] 表示二进制表示法下是 i 的子集的数的个数，其中有 g[i] 个于 i 相同。

那么 i 对 Ans 的贡献就是

重点就是 f[i] 的统计。

如果是普通的枚举，那么复杂度将会达到 O( \Sigma C_n ^ k \cdot 2 ^ k ) ， n 可以达到 20 ，这会是 TLE 级别的复杂度(不想算。。但是在 k = 10 的时候就已经有亿万级别了)。

(复杂度的计算是这样的，每个状态被自己的所有子集更新一次，子集个数是 2 ^ k ， k 是状态中 1 的个数。那么 1 的个数是 k 的状态个数是 C_n ^ k ，也就是上述的那样。在 k = 10,\ n = 20 时，大小为 189190144 )

我应该没算错QAQ。

所以我们需要用到高维前缀和。

初始时 f[i] = g[i] ，然后

loop i from 0 to 21 : // 枚举直接转移(通过某一位上的1)
    loop S from Maxn to 0 : // 枚举状态
        if (S & (1 << i)) dp(S) += dp(S ^ (1 << i)) // 如果可以更新

注意枚举转移放在了外层循环，而不是内层，否则就会重复许多。

下面证明这样子对于所有的 S 而言，更新到了其全部的父亲并且没有重复更新。

这里我们建一个图，当且仅当 S 能通过改变一个 0 为 1 变为 S' 时，从 S 为起点，向 S' 连边，于是一条边就对应着代码里的一次转移。

比如说 000 可以向 010, 001, 100 连边，但是不能向 011 连边，因为它改变了两个 0 为 1 。

那么， 3 位的图就是这个样子

这张图也可以很好的解释为什么在内层循环枚举转移会重复，因为每次把每个状态的所有边同时走了一遍。

可以发现在每一层的节点中， 1 的个数都是相同的，并且上下两层呈递增关系。

每走一条边，就对应着代码里一次更新，也就是相当于把 到达过 当前状态 S 的点累积到 S' 中。

(用“到达过”是因为加了之后不会去掉)

对于某个 S 及其任意一个父亲 S' ，设 t = S' - S ，也就是二者的差。

假设 t 中 1 的个数为 cnt ，那么 S 需要走 cnt 条边才能到达 S' 。