题解 P6020【[Ynoi2010] Exponential tree】

[P6020 [Ynoi2010] Exponential tree](https://www.luogu.com.cn/problem/P6020) 解题报告： [更好的阅读体验](https://www.cnblogs.com/xiaoziyao/p/16676217.html) 感觉还是水平不太行，写的很感性。 ## 题意 给定 $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$。 ## 分析 ~~之前学习过[相关知识](https://www.luogu.com.cn/blog/qwaszx/jing-tai-ou-jian-jie-ge-lv-xin-xi-zha-xun)，结果又不会了，属实是菜。~~ 记 $F(k,n)$ 为在 $(k,n)$ 约束下我们做到的 $m$ 大小。 赋予矩阵一个组合意义：我们初始拥有 $n-1$ 个区间 $[i,i+1]$，需要预处理若干个区间，使得预处理的区间都可以表示成两个更小的预处理区间的无交并，且所有的区间都可以表示成不超过 $k$ 个预处理的区间的无交并。 $k=2$ 时是经典的猫树算法，这里不赘述，可以做到 $F(2,n)=O(n\log n)$，事实上这也是这个子问题的[下界](https://www.luogu.com.cn/blog/EntropyIncreaser/noi2022-count-analysis)。 $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))$。 ## 代码