阈值分治的高端应用：记两道 HDU 多校

· · 算法·理论

【已经收入文章《每日一技》。】

你说得对但是出题人可以把阈值分治玩成花。

下面除法都下取整。

Counting good arrays - HDU 多校 2022 第七场 1009

有趣的题。

首先进行一个题目的转化：将 a 数组转化成一个二元组序列 b=\{(w_i,p_i)\}，表示所有 \{p_i\} 满足 w_i=\frac{a_{p_i}}{a_{p_{i-1}}}>1。特别地，我们设 a_0=1。

容易发现这个转化是双射，且 |b|\le\log m。那么现在的问题就转化为了求可能的 b 的个数。

考虑 dp。最暴力的方法是我们设 F(i,x) 表示，p_i=i,W_j=\prod_{j\le i}w_j=x。转移时直接枚举 x 的因数转移。复杂度是 \Theta(m\log^2m) 的（状态 m\log m，转移 \log m）。最后统计答案时枚举长度 p，答案加上 \binom{n+1}{p+1}\sum_xF(p,x)（因为 \sum_{i=0}^n\binom ip=\binom{n+1}{p+1}）。

然后考虑优化。根号分治！我们设一个 B=\sqrt m，钦定 w_{j+1}\ge B。那么方案数为 F(j,W_j)\times\sum_x F(p-1-j,\frac{x}{W_{j+1}})。我们考虑设 W_j=x,\frac{m}{W_{j+1}}=y。那么有 x\le B,y\le\frac mB。

于是我们的柿子就可以更紧凑地写为

\begin{aligned} &\sum_{j=0}^{p-1}\sum_{x=1}^B\sum_{y=1}^{\frac mB}\left(\frac{m}{xy}-\frac Bx\right)F(j,x)F(p-1-j,y)\\ =&\sum_{j=0}^{p-1}\sum_{x=1}^BF(j,x)\sum_{y=1}^{\frac mB}\left(\frac{m}{xy}-\frac Bx\right)F(p-1-j,y) \end{aligned}

其中减掉的是 W_{j+1}\le B 的情况。发现这样 F 只要处理到 B 范围了。但是总复杂度没变，咋办？

最后一个 sigma 里的东西显然可以数论分块。对 F 作前缀和，先把 \frac Bx 拆出来单算（只用一遍前缀和），再数论分块计算前面的一项，这样就能快速计算 \frac{m}{xy} 相同的区间了。这样如果实现很优秀的话甚至能做到 \Theta(m^{\frac 23}\log m)！加上前面预处理的复杂度就是 \Theta(m^{\frac 23}\log m+\sqrt m \log^2m)。

为啥不改 B 的块长呢？因为前面的带两只老哥的部分要预处理到 \max(B,\frac nB)。实测取 B=m^{0.47} 时最优。

极限数据自测 1s，HDU 5.5s，大唐高鸿 40s！于是训练赛时一直以为不能过，加了很多优化，比如再对行做前缀和同时取消枚举 p、取模最后一起再取等等。

std \Theta(m^{\frac 34}\log m) 太菜了。

这是一道比较中规中矩的根分。那么下一道是不是根分呢？

Multiply 2 Divide 2 - HDU 多校 2022 第六场 1001

也是很有趣的题目啊！

首先注意到我们最终的 a'_i 一定是 (\frac{a_i}{2^p})\times 2^q 的形式。因为如果有相邻的先乘后除那么可以消掉，所以肯定不优。

所以我们有了个 \Theta(n\log^3m) 的 dp：F(i,p,q) 表示 a_i 使用了 p 次除，q 次乘。注意这里 q 是 \log^2 级别，否则会被同场的 1002（1001 的一个 Hack）卡掉。

发现这样炸了，怎么办呢？考虑倒着进行这个 dp，且增加一个条件：a'_i>M=100000。我们设分界线 j：1\sim(j-1) 是 a'\le M, j\sim n 是 a'>M。

先考虑后面：倒着对 j\sim n dp。注意到倒着的时候，最前一个数 a'_j 必须贴着 M 的线。那在前面增加一个数时，在 a'_j>a'_{j+1} 的时候额外加上 n-j 的花费就行了（代表后面都多乘一个二）。那么 q 没了！！！只剩了两维，i 和 p（因为有准线了），这样后面暴力转移做到了 \Theta(n\log^2M)。

再考虑前面。前面还是使用开头的 dp 方式，这时 q 降到了 \log 级别。再重新考虑这个 dp 的细节，做到转移常数级别。发现随着 (\frac{a_i}{2^p})\times 2^q 的增大，转移范围严格单增，对转移进行一个前缀 \min 优化就成 \Theta(1) 了，总复杂度 \Theta(n\log^2M)。

这道题就解决了。

有一个问题就是我们的阈值 M 为啥不能设的很小呢？有一个大前提就是前面的“贴着 M 的线” 也就是说如果最优的 a'_1<M 那么这个做法就寄了 但是可以证明 a_1 不会变大（否则不优），所以 M>a_1，取 M=100000 是极好的。

注意卡空间，必须得把 p 和 q（\le 17）从 int 改成 char 存。

关于习题：这两道都是关于数论的，但是不记得其余的关于数论的根号分治好题了/ng。于是凑个数：