题意省流:假概率计数题,保留 K 位输出,其中 K≤30。
且不论未定精度在输出上卡选手一下,这个 K≤30 意味着 long double 跑不了了,于是题解区的大伙掏出了 __float128 或手写高精度。但是这两个东西都跑得贼慢,于是大伙不约而同地使用了:
- 若 K≤8 则用
double / long double;
- 否则用
__float128。
这不是纯纯人类迷惑行为吗?我 n 的大小跟 K 又没有关系,这个判断意义何在呢?
于是我拿下来每一篇题解,用极限数据 100 0 30 跑一遍,电脑配置 NOI linux 2.0, Intel® Core™ i5-9500T CPU @ 2.20GHz × 6 ,编译选项 -std=c++14 -Wall -O2,每一篇题解都要 15 至 20 秒甚至更多才能跑完。然后我又把最优解拿下来测了测,他也要跑 9s+。
在好奇心的驱使下,我去 assert 了一下数据,结果 K=30 的点里 n 最大只有 50。
[汗][汗][汗][汗]
明明这题只需要固定精度或者加个取模就可以避免这么多问题,但是出题人他偏不,就喜欢在这种地方加『难度』。这还是省选题,不知道他想要区分谁出来。场上选手发现自己极限数据过不去疯狂卡常然后你告诉他嘿嘿没有极限数据你需要按数据分治我相信是个人都会攥紧拳头痛骂出题人不是人。
于是这个题怎么办呢?你直接把 hack 加到 0 分 subtask 那么恭喜所有人都 unaccepted100 了。我的建议是把主题库的这个题题面改一下就令 K≡8 或者 K≤8 然后再在 U 字题目里把这个题原汁原味地端上来谁爱写谁写。