跳转至

分段打表

在学习之前请先学习 分块

打表大家都知道,就是在比赛时把答案都输出出来,然后开个数组,把答案直接存入数组里。于是你的代码时间复杂度就是 O(1) 的了。

但是需要注意这个技巧只适用于类似输出某函数值类的问题。比如规定 f(x) 为整数 x 的二进制表示中 1 的个数。输入一个正整数 n ,输出 \sum_{i=1}^nf^2(i) 。这样的话 n 不大时,采用打表的方法可以做到 O(1) 的复杂度。

注意到这个问题其实十分的简单,采用一般做法也可以做到 O(n\log n) 的复杂度,但是 n=10^9

还有一些时候,打出来的表十分大,如果对于每一个 n ,都输出 f(n) 的话,那么 MLE 之外,还有可能代码超过最大代码长度限制,导致编译前不通过(代码可能直接被 pass)。

我们考虑优化这个答案表,借用分块思想,我们设置一个合理的步长 m (这个步长一般视代码长度而定),对于第 i 块,输出:

\Large \sum_{k=\frac{n}{m}(i-1)+1}^{\frac{ni}{m}} f^2(k)

的值。

然后输出答案时借用分块思想处理即可。

一般来说,这样的问题对于处理单个函数值 f(x) 很快,但是需要大量函数值求和(求积或某些可以快速合并的操作),枚举会超出时间限制,在找不到标准做法的情况下,分段打表是一个不错的选择。

注意事项

  1. 当上题中指数不是定值,但是范围较小,也可以考虑打表;
  2. 上题是本人为了介绍分段打表口胡出来的,如已有此题纯属巧合。

例题

「BZOJ 3798」特殊的质数:权限题……不过可以在各大 BZ 离线题库中看到。

题意简述:求 [l,r] 区间内有多少个质数可以分解为两个正整数的平方和。—— via PoPoQQQ

「Luogu P1822」魔法指纹:其实是一道暴搜,不过可以练练分段打表。

明明是我先写的分段打表为什么你们这么熟练 QAQ,可以对比下我的题解的发布时间和 Luogu 中的。


评论