分段打表

前置知识：分块。

朴素的打表，指的是在比赛时把所有可能的输入对应的答案都计算出来并保存下来，然后在代码里开个数组把答案放里面，直接输出即可。

注意这个技巧只适用于输入的值域不大（如，输入只有一个数，而且范围很小）的问题，否则可能会导致代码过长、MLE、打表需要的时间过长等问题。

例题

规定为整数的二进制表示中的个数。输入一个正整数 ( $n\leq 10^9$ )，输出 $\sum_{i=1}^n f^2(i)$ 。

如果对于每一个，都输出的话，除了可能会 MLE 外，还有可能代码超过最大代码长度限制，导致编译不通过。

我们考虑优化这个答案表。采用分块的思想，我们设置一个合理的步长（这个步长一般视代码长度而定），对于第块，计算出：

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

的值。

然后输出答案时采用分块思想处理即可。即，整块的答案用预处理的值计算，非整块的答案暴力计算。

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

注意事项

当上题中指数不是定值，但是范围较小，也可以考虑打表。

例题

「BZOJ 3798」特殊的质数：求区间内有多少个质数可以分解为两个正整数的平方和。

「Luogu P1822」魔法指纹

本页面最近更新：2023/2/18 07:57:07，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：billchenchina, ouuan, Chrogeek, Enter-tainer, Great-designer, greyqz, Henry-ZHR, HeRaNO, Ir1d, Junyan721113, Macesuted, sshwy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用