P8478 清明的亚指数时间做法

“何必偷光赐我以绚烂却徒留不甘”

本题存在亚指数时间做法，把题解区里一堆做法拼起来就可以做出来，在此给出一种可以在 $exp (O (n lo g n))$ 时间内理论解决本题的做法。

参考了官方题解与 ningago 的题解在 $k > n /2$ 时的多项式时间做法。

如果你已经完全掌握官方的 $O^{*} (2^{n /2})$ 时间的做法，可以直接跳至 Part3 开始阅读，本文对前半部分的叙述比较 abstract，如有不理解可以参考其他题解。

Part1. $O^{*} (2^{k})$

令第 $i$ 层向 $j$ 层流出的水量为 $c_{i, j}$ ，若 $i > j$ 或 $j - i > k$ 时 $c_{i, j} = 0$ 。

则要求等价于对所有合法的流量矩阵，即满足 $\sum_{j = i}^{i + k} c_{i, j} = a_{i}$ （每一层留给自己和后 $k$ 层水量的和确定）的所有 $c$ 数组，求 $\prod_{j = 1}^{n} (\sum_{i} c_{i, j})$ 的和。（这个过程形如“行和确定，分配给列” and then “对列和求乘积”）

面对这种 $\sum (\prod (\sum))$ 形式且值域极大、难以计算的式子，我们的想法自然会是用乘法分配律（组合意义）把里面 $\prod (\sum)$ 拆出来，变成对于所有合法的限制，求 $\sum_{满足条件} \prod$ 的形式。

考察拆开括号 $(c_{1, 1}) \times (c_{1, 2} + c_{2, 2}) \times (c_{1, 3} + c_{2, 3} + c_{3, 3}) \times \dots \times (\dots)$ 这样的括号，我们等于要在每个括号内选取恰好一项，并求其在所有满足限制情况下乘积的和。我们假设第 $j$ 个括号选取了项 $c_{f (j), j}$ 。最终的乘积就是 $\prod_{j = 1}^{n} c_{f (j), j}$ 。我们再按照每一个限制的顺序，考虑去满足第一个 $\sum$ 上的这些限制，我们依次考虑：对于每个 $i$ 限制的和 $a_{i}$ ， $c_{i, j}$ 出现在了哪些 $j$ 的括号里。

这个时候可以发现对于一组确定选取的 $f (1) \dots f (n)$ ，我们并不关心它们各自的值，只关心每个 $f$ 构成的可重集 ${f (j)}$ 。因为限制之间是独立的，而我一旦知道了对于一个限制 $\sum_{j} c_{i, j} = a_{i}$ 有 $T_{i}$ 个 $c_{i, j}$ 被选入乘法里了，那么所有 $c_{i, j}$ 的项对整个乘法的贡献就确定了，就是若干个独立的下面这个问题：

”所有长度为 $k + 1$ ，和为 $a_{i}$ 的自然数序列的某 $T_{i}$ 项的积的和是多少？“（因为每个位置等价，不妨转成前 $T$ 位，这里的 $k$ 和 $n - i$ 取个 min，即实际的窗口长度)

而这个问题是简单的，有很多种方式统计出，用组合意义把它看成 $a_{i}$ 个无标号球进 $k + 1$ 个盒子，前 $T$ 个盒子再选一个球的方案数。转置顺序后等于先选 $T_{i} + k$ 个特征点出来，交替设置为球和板子，可以直接插出来答案是 $(T + k a _{i} + k)$ 。

于是对于一组确定的 $T_{i}$ （由某种括号内选择方案生成出的每个限制被选取的次数），我们可以快速算出满足所有限制的方案的乘积的和，它们之间独立，我们将其相乘。

接下来我们就可以直接按 $i$ 的顺序生成 $T_{i}$ ，枚举任意一个目前未确定 $f$ 的 $j$ 的集合的子集，然后将其设为已选择并产生一个仅和这个集合大小相关的系数。仅需记录 $2^{k}$ 个状态，即可能被选择的之后 $k$ 个括号是否被占据即可。

直接转移可能会带有一个枚举子集的 $O (3^{k})$ ，然而我们本质是在做子集卷积，甚至第二个幂级数的大小也只和集合大小相关，所以可以再开一维表示增加的量，做高位前缀和就行。

时间复杂度 $O (n^{3} 2^{k})$ 。

该做法在 $k = n - 1$ 时，我们不再关心之后具体被占据的是哪些括号了。可以直接从后往前 dp 的过程中，直接用一个数来记录目前还有几个括号没有选出。容易做到 $O (n^{3})$ 。

Part2. $O^{*} (2^{n - k})$

注意到 $k$ 较大的时候整个问题是很接近 $k = n - 1$ 的问题，只是在后 $n - k - 1$ 个位置的 $f (j)$ 不能被所有括号取到，而其它都可以任意选择。所以我们考虑继续仿照着 Part1 的办法，仍然从后往前 dp，只是再多记录一个 $2^{n - k}$ 个 bit 表示最后几个位置是否被占用，而其它位置都等价，因此我们只需要记录数量即可，从后往前 dp 就行，直接做就可以做到 $O (n k^{3} 2^{n - k})$ 。

官方给了一个精妙的容斥方式，我们直接通过容斥来枚举并钦定后 $n - k - 1$ 项是否选择超出 $k$ 距离的位置，用无限制减掉超出，如果钦定了位置 $j$ 超出，就视作这个位置 $j$ 上并没有一个可以选择的括号，而是直接在 $j - k - 1$ 的时候加入一个括号（这样它选择的就一定是一个之前距离超过 $k$ 的数）；如果不钦定，就直接在 $j$ 位置上有一个括号，可以被前面所有数选择。

枚举这 $n - k - 1$ 个位置的 $2^{n - k - 1}$ 种超出情况，这个时候每种都是在每个位置上有若干括号，然后每个数可以出现在之后的所有括号里，出现 $T_{i}$ 次会产生一个和 $T_{i}$ 有关的乘法系数，和 part1. 的 $O (n^{3})$ 做法完全相同，从后往前做即可。

时间复杂度 $O (n^{3} 2^{n - k})$ 。

Part3. $k^{O (n / k)}$

参考了 ningago 的题解。

对于这种序列上两个位置差不超过 $k$ 才能互相影响的题目，我们有一种尝试的策略：将其分为长度为 $k$ 的段，这样我们需要考虑的影响就只有两种：组内的任意匹配；对于相邻两组，前组的第 $i$ 个和后组的第 $j$ 个（ $i > j$ ）。

灵感来源1 灵感来源2

我们现在将序列分成 $⌈ \frac{n}{k + 1} ⌉$ 组，每一组长度为 $k + 1$ ，组内的位置之间距离都 $\leq k$ ，一个数是可以出现在组内之后的任意括号的，而对于相邻两组，前组的第 $i$ 个数可以出现在后组的前 $i - 1$ 个括号。我们把它每组一行化成这样一个图。

于是我们尝试将限制 $i$ 可能选择的括号的两部分分别考虑：同行后面的，任意选，只关心每行后面还可以被选择括号的数量；以及它提前”占用“ 了多少下一行的括号：下一行的第 $i$ 个位置之前的括号都可以被预支。

所以我们可以并行地从后往前推进 $i$ ，这样每行的位置就被 $i$ 之前和 $i$ 之后分成了两部分， $i$ 之前只会被预支给上一组的 $i$ 之后的位置，我们只关心预支了多少个括号；而 $i$ 之后的位置只能提供给这一组，我们只关心剩下了几个括号还能被选。

拿 ningago 的题解中的 $k > n /2$ ，即两组的情况举例，我们可以这样 dp：

让 $f_{i, r e m_{1}, p r e_{2}, r e m_{2}}$ 表达：目前已经从后往前考虑到每组的第 $i$ 个限制所带来的系数，其中：

第一组 $i$ 及之后还剩下了 $r e m_{1}$ 个括号可以选
第二组 $i$ 之前有 $p r e_{2}$ 个括号被第一行的 $i$ 及之后的括号用了
第二组 $i$ 及之后还剩下了 $r e m_{2}$ 个括号可以选

如果不考虑 $i$ 本身这个括号，有这些组合结构上的系数：

第二组部分带来的系数是简单的，枚举这个数出现在了 $occ$ 个括号，这决定它本身的乘法系数，然后组合结构上直接在之后 $r e m_{2}$ 个里面选 $occ$ 个，即 $(occ r e m _{2})$ 。

第一组部分带来的组合系数，枚举两个部分：这个数出现在了 $s am e$ 个同组括号中， $n e x t$ 个第二组的括号中，组合结构上的系数就是： $(s am e r e m _{1}) (n e x t p r e _{2} + n e x t)$ 。第二部分表示重排目前的待补预支队列。

考虑 $i$ 这个括号本身，需要在这两个系数上增加三种情况： $i$ 这个括号被选给自己， $i$ 这个括号被上一组预定了， $i$ 这个括号留给这一组的 $i$ 之前的位置，会分别对 $occ$ ， $p r e_{2}$ ， $r e m$ 有 $\pm 1$ 的影响。

所有括号都安排好自己选择的数，并且每行被预支括号都还清的情况下， $f_{0, 0, 0, 0}$ 就是答案。

于是我们可以在 $O (k^{6})$ 的时间内解决分两组的情况。

因为只可能相邻的两组之间才会有影响，所有这个做法完全可以扩展到有更多组的情况：我们并行地从后往前做每个组，需要记录在状态中的的东西依然形如

r e m_{1}, p r e_{2}, r e m_{2}, p r e_{3}, r e m_{3} \dots p r e_{n}, r e m_{n}

分别代表每一组 $i$ 之后剩余的可以选择的括号里量，以及每一组被前一组预支的括号量，转移和在两行的情况下第一行的行为几乎完全相同。

总共有 $q$ 组，我们总共要记录 $q$ 个余量和 $q - 1$ 个预支量，对于每个 $i$ ，总状态量是 $(k + 1)^{2 q - 1}$ ，转移总是 $O (k^{2})$ 的，复杂度可以做到 $O (n k^{2 q + 1})$ ，即 $O (k^{O (n / k)})$ 。

Part4. $exp (O (n lo g n))$

在获得了 Part3 的 $O (k^{O (n / k)})$ 时间的做法后，接下来的拼接就是很经典的数据分治，指数拼分组并行，这个平衡思想和多串最长公共子序列问题和最长非本原串问题的 $exp (O (n lo g n))$ 做法完全一样。（另一个同款思路题目）

在 $k$ 较小时，直接采用 Part1 做法， $O^{*} (2^{k})$ 地记录被占用的位来统计，而在 $k$ 较大时，采用 Part5 的做法，并行地通过 dp 统计 $n / k$ 个长度为 $k$ 的组来完成，时间复杂度 $k^{O (n / k)}$ 。

取平衡点 $k^{O (n / k)} = O (2^{k})$ 时，两边同时取 log， $O (\frac{n}{k} lo g k) = k$ ，取 $lo g k = O (lo g n)$ ，得 $k = O (n lo g n)$ ，此时两侧时间均不高于 $exp (O (n lo g n))$ 。

这个优化在本题数据范围下难以展示更多分割的优越性了，本题数据范围下比较容易做到 $O (2^{n /3} poly(n))$ 优于目前最优解。那个真正分 $n / k$ 组的做法有点变态，有人愿意吃的话可以来写一下，感觉在本题的数据范围下跑不快就是了。

“哪怕唯有余辉能抵达

我依然会为你献上最后的盛大”

P8478 清明的亚指数时间做法

Part1. $O^{*} (2^{k})$

Part2. $O^{*} (2^{n - k})$

Part3. $k^{O (n / k)}$

Part4. $exp (O (n lo g n))$

评论

写下你的评论

Part1. O∗(2k)

Part2. O∗(2n−k)

Part3. kO(n/k)

Part4. exp(O(nlogn​))

评论

写下你的评论

Part1. $O^{*} (2^{k})$

Part2. $O^{*} (2^{n - k})$

Part3. $k^{O (n / k)}$

Part4. $exp (O (n lo g n))$