AIOJ

Prerequisite: block decomposition.

Naive table precomputation means calculating and saving the answers corresponding to all possible inputs during a contest, then putting the answers in an array in the code and outputting them directly.

Note that this technique only applies to problems with a small input value range (for example, the input consists of only one number and its range is very small). Otherwise, it may cause the code to be too long, result in MLE, or take too long to precompute the table.

Example

Let $f(x)$ be the number of $1$ s in the binary representation of the integer $x$ . Given a positive integer $n$ ( $n\leq 10^9$ ), output $\sum_{i=1}^n f^2(i)$ .

If we output $f(n)$ for every $n$ , in addition to possibly causing MLE, the code may exceed the maximum code length limit and fail to compile.

We consider optimizing this answer table. Following the idea of block decomposition, we set a reasonable block size $m$ (this size generally depends on the code length). For the $i$ -th block, calculate the value of

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

The value.

Then process the answer using the block decomposition idea when outputting it: use the precomputed values for complete blocks and calculate incomplete blocks by brute force.

Generally speaking, problems of this kind allow a single function value $f(x)$ to be computed very quickly, but require summing many function values (or computing products or other operations that can be merged quickly). Enumeration would exceed the time limit, so when no standard approach can be found, blockwise precomputation is a good choice.

Notes

If the exponent in the problem above is not fixed but has a small range, table precomputation can also be considered.

Examples

BZOJ 3798 Special Primes: Given an interval $[l,r]$ , find how many primes in it can be expressed as the sum of the squares of two positive integers.

Luogu P1822 Magic Fingerprint

Blockwise Precomputation

Examples