WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数学部分简介
符号
复数
位运算
快速幂
进位制
高精度计算
平衡三进制
素数
最大公约数
欧拉函数
筛法
欧拉定理 & 费马小定理
类欧几里德算法
裴蜀定理
乘法逆元
线性同余方程
中国剩余定理
二次剩余
BSGS
原根
卢卡斯定理
莫比乌斯反演
杜教筛
Min_25 筛
分解质因数
多项式部分简介
拉格朗日插值
快速傅里叶变换
快速数论变换
快速沃尔什变换
多项式求逆
多项式开方
多项式除法|取模
多项式对数函数|指数函数
多项式牛顿迭代
多项式多点求值|快速插值
多项式三角函数
多项式反三角函数
常系数齐次线性递推
生成函数简介
普通生成函数
指数生成函数
向量
矩阵
高斯消元
线性基
线性规划简介
单纯形算法
排列组合
卡特兰数
斯特林数
贝尔数
伯努利数
康托展开
容斥原理
抽屉原理
概率初步
置换群
斐波那契数列
博弈论
牛顿迭代法
数值积分
分段打表
64 objects
本站非官方,所收集资源均来源于网络。
分段打表 - 数学
前置知识: [分块](/ds/decompose/) 。 朴素的打表,指的是在比赛时把所有可能的输入对应的答案都计算出来并保存下来,然后在代码里开个数组把答案放里面,直接输出即可。 注意这个技巧只适用于输入的值域不大(如,输入只有一个数,而且范围很小)的问题,否则可能会导致代码过长、MLE、打表需要的时间过长等问题。 ### "例题" > 规定 $f(x)$ 为整数 $x$ 的二进制表示中 $1$ 的个数。输入一个正整数 $n$ ( $n\leq 10^9$ ),输出 $\sum_{i=1}^n f^2(i)$ 。 如果对于每一个 $n$ ,都输出 $f(n)$ 的话,除了可能会 MLE 外,还有可能代码超过最大代码长度限制,导致编译不通过。 我们考虑优化这个答案表。采用 [分块](../ds/decompose/) 的思想,我们设置一个合理的步长 $m$ (这个步长一般视代码长度而定),对于第 $i$ 块,计算出: $$ \sum_{k=\frac{n}{m}(i-1)+1}^{\frac{ni}{m}} f^2(k) $$ 的值。 然后输出答案时采用分块思想处理即可。即,整块的答案用预处理的值计算,非整块的答案暴力计算。 一般来说,这样的问题对于处理单个函数值 $f(x)$ 很快,但是需要大量函数值求和(求积或某些可以快速合并的操作),枚举会超出时间限制,在找不到标准做法的情况下,分段打表是一个不错的选择。 ### "注意事项" > 当上题中指数不是定值,但是范围较小,也可以考虑打表。 ### 例题 [「BZOJ 3798」特殊的质数](https://www.lydsy.com/JudgeOnline/problem.php?id=3798) :求 $[l,r]$ 区间内有多少个质数可以分解为两个正整数的平方和。 [「Luogu P1822」魔法指纹](https://www.luogu.com.cn/problem/show?pid=P1822)