自动搬运

查看原文

来自洛谷，原作者为

	whiteqwq 寻找着梦与现实的交点 在哪呢 在哪呢

搬运于2025-08-24 22:16:35，当前版本为作者最后更新于2022-09-10 11:19:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P6020 [Ynoi2010] Exponential tree 解题报告：

更好的阅读体验

感觉还是水平不太行，写的很感性。

题意

给定 $n,k$，构造矩阵满足：

1. $a_{i,i}=a_{i,i+1}=1$；
2. 对于 $i>j$，$a_{i,j}=0$；
3. 若 $j>i+1$ 且 $a_{i,j}=1$，则存在 $i<t<j$ 满足 $a_{i,t}=a_{t,j}=1$；
4. 矩阵 $A^k$ 需满足对于所有 $i\leqslant j$，$(i,j)$ 非零。

数据范围：

$1900\leqslant n\leqslant 2000$，$2\leqslant k\leqslant 15$，你构造的矩阵 $1$ 个数 $m$ 需要服从一系列约束，形如 $m-(2n-1)\leqslant \lambda n$。

分析

之前学习过相关知识，结果又不会了，属实是菜。

记 $F(k,n)$ 为在 $(k,n)$ 约束下我们做到的 $m$ 大小。

赋予矩阵一个组合意义：我们初始拥有 $n-1$ 个区间 $[i,i+1]$，需要预处理若干个区间，使得预处理的区间都可以表示成两个更小的预处理区间的无交并，且所有的区间都可以表示成不超过 $k$ 个预处理的区间的无交并。

$k=2$ 时是经典的猫树算法，这里不赘述，可以做到 $F(2,n)=O(n\log n)$，事实上这也是这个子问题的下界。

$k=3$ 时是经典的 sqrt-tree 算法，做法大概是对序列分块，预处理所有块前缀、后缀区间，以及所有整块区间，块内的区间作为子问题递归处理，得到 $F(3,n)=O(n\log\log n)$。

$k>3$ 时，想做到更优，我们需要对整块区间也作为子问题处理。

具体地，我们可以通过 dp 找出最优的分段点：（令 $a_{1,2,\cdots,p}$ 为每一个块的大小）

$$F(k,n)=\min_{a_{1,2,\cdots p}}(a_1-1)+\sum_{i=2}^{p-1}(2a_i-3)+(a_m-1)\\+F(k-2,p-2)+\sum_{i=1}^p F(k,a_i-[i>1]-[i<p]) $$

直接求复杂度太劣，剪一剪枝大概就能过了。

---

稍微提一句，当 $k=O(\alpha(n))$ 时，我们可以做到 $F(k,n)=O(n\alpha(n))$（应该是下界？），做法大概是：

建立 $t$ 层数据结构，其中第 $i$ 层数据结构块间用第 $i-1$ 层数据结构维护（我们钦定第 $0$ 层的数据结构为猫树），块内递归下去。

令 $T(t,n)$ 为第 $t$ 层数据结构的深度，我们第 $i$ 层数据结构按照 $T(i-1,n)$ 分块，于是 $T(1,n)=\log^*n$，$T(2,n)$ 就是 $n$ 不断取 $\log^*$ 直到变成 $O(1)$ 的次数。那么 $t$ 就是 $n$ 不断变成 $T(t-1,n)$ 变成 $O(1)$ 的次数，此时 $t=\alpha(n)$，为反阿克曼函数，于是得到 $F(k,n)=O(n\alpha(n))$。

代码