致敬传奇分段打表大师 zhangjinxuan
本帖最后由 zhangjinxuan 于 2024-10-17 21:27 编辑1924 年秋，窗外刮着海啸，鸟儿在绽放，花儿在歌唱。
昏暗的电脑前坐着的神经焕发的小伙就是主人公，他用了 1 小时就拿到了最简单的大众分（虽然并没有 AK）。
此时他打开最后一道题，这道题是一道喜闻乐见的数学题，题目是这样的：
> $f_1=1,f_i=f_{i-1}+f_{\lfloor \frac{i}{2} \rfloor}$，$200$ 次询问，求 $f_n$。
毫无头绪的他看了一眼数据范围，除了 $n\le 10^{6}$ 以外他还看见了一个东西，$n\le10^{9}$，整整 **25** 分。这个东西如同拥有者魔力吸引着他，他陷入了着迷。
回想起上午遇到的一个 $10^{9}$ 组合数而询问很小的一道题目，他神经发作，联想到了一个很厉害的东西，**分段打表！**
$1\text s$，$512\text {MB}$，$100 \text {KB}$，有分就很厉害了！
他便踏上了这个一去不复返的路。类似 $10^{9}$ 组合数，他将 $1\sim 10^{9}$ 的部分 $f$ 直接求出来，步长为 $10^{6}$，存在一个 map 里面，直接记忆化搜索即可。
不愧是记忆化搜索大师！只有 $10\text K$，然而样例跑了 $30\text s /2\text G$。
仍然是一个不错的开始！他突然想到 map 的常数依托，而且太大的也不很好优化代码长度，所以他暂时放弃这个想法。
想到必要用 map 存这些，只要访问到 $i$ 就判断 $i\equiv0\pmod {10^{6}}$ 就可以了。
进行优化之后，更慢了，他有想到可以与 map 结合，这样，样例就被优化到了 $10\text s /1\text G$！
很好的结果！！！他显然也想到了，只要更改步长和预处理的个数，就可以很好地提升效率！于是他把步长改为了 $100000$。
使用 Lemon 自测时却发现“找不到选手程序”，原来是大小太大了，足足 $300\text{KB}$，于是他只能先把压缩的问题放在一边，暂且只有十六进制，然后发现优化到了 $5\text s/800\text{MB}$。
即使是最终评测时的上帝的电脑，也带不动。一时间情况变得焦灼。
他突然灵光一闪——既然我的打表程序能直接求 $10^{9}$ 了，那我的最终程序不也可以？放一个 $10^{8}$ 就差不多了！
他继续了这痛苦的调试，但想到 $25$ 分能超过 $25$ 个操场的人，他又有了源源不断的动力。
于是他直接写出了一份很优秀的代码！长度 $247\text{KB}$，被优化到了 $1.2\text s/750\text{MB}$！
差点意思，调调步长？越来越大了，但是也终于跨越了第一座里程碑：一秒，只用了 $0.99$ 秒！。证明了这个方案是可行（逝）的！
他便开始使用压缩，由于答案是需要对 $998244353$ 取模的，所以数字不是很大。原本使用十六进制不仅有 0x 前缀，而且有很多的浪费，他思考更好的进制，显然就是取字符 $\texttt 0$ 到 $\texttt z$，之间 $75$ 个字符，也就是 $75$ 进制。
手写了一个即为简易的加密解密，用字符串存储呗，非常简易。
长度被优化到了 $173\text{KB}$，然而时间更慢了，原来是每访问一次就解密，不如预先就解密好。
他却突然发现空间也有点问题，所以他继续减小了步长，哟，空间 $510\text{MB}$，长度又废了。
此时已经过去了 $1.5$ 小时，一分没做，但是他却认为，**我既然都来了。**
此时他的大脑充满了疯狂，突然想到非可见字符也是可以存在代码里面的，于是他直接取了 ASCII $16\sim126$ 的所有字符，厉害的 $111$ 进制！
他又注意到 $\texttt ",$ 这两个东西分隔两个字符串太愚蠢了，直接把长度对齐拼成一个串就好了！
很好！长度 $75\text{KB}$，$\text{1.5s}/400\text{MB}$，他似乎快逃离了苦海！
吗？WA 了？？！
原来是转义字符的锅，改了一下还是过不了。
他怀疑是因为长度对齐拼成一个串出了问题，怀疑的不错，因为改回来就能对了，但是 $173\text{KB}$。
为什么是这里的问题？？哦，原来长度对齐不应该是 $4$，因为 $111^{4} \le 998244353$，所以他改为了 $5$，长度 $96\text{KB}$。
突然，CE 了，大量乱码直接出现在终端屏幕上，瞬间使得终端崩溃。
原来是表数组开小了，改成 $10^{5}$ 就行。
还是不对？？？经过痛苦地排查发现，原本 $14800$ 个数字，经过压缩对齐之后，却变成了 $73998$ 的长度，莫名其妙少了 $2$。
各种的 `assert` 都排查了，怎么可能会有两个漏网之鱼呢？
反复调试之后，他终于通过了第一个询问！测试全部时！
第二个 WA 了。而且 $1.7\text s/612\text{MB}$。
不是哥们 $17:20$ 还有 $20$ 分钟结束了你跟我玩这一出？？？
此时，他才意识到情况不对，但为时已晚，通过探明他人战况所知，它们获得了 $330$ 的高分，自己呢？$2.5$ 小时之前 $190$，现在获得了 $±0$ 分，被同学嘲笑了 inf 次。
再一次看着满是乱码的不可读程序，心中充满了绝望。
于是他释怀地死了。
珍爱生命，远离打表。 模拟赛的一个功能就是练习时间分配{:10_266:} {:7_113:} 这么弱智的人怎么没人看乐子啊 {:10_256:}{:10_256:} {:10_254:}{:10_254:}
页:
[1]