众所不一定周知,某开小号的匿名毒瘤把 dp 状态哈希,使得复杂度不优的方法通过了此题。今天闲着无聊小编芙卡米重读了毒瘤的题解,结果发现有一句话:
特判无解的话我们用这份哈希+记搜的代码跑一下,然后打个表,发现在 n 取 1∼233 时,10∣p 或 p=25 或 p=26 时总是无解的。
10∣p 无解很有道~理~,因为尾数取不到 0;p=25 无解也有道~理~,因为位数取不到 25,50,75;但是 p=26 又是怎么一回事呢?于是小编拿之前的 std 跑了下,发现 p=26 确实是有解的。小编不太放心,于是拿了另一篇题解,发现跑出来也有解。那么毒瘤为什么会通过呢?原来是出题人之前的数据里没有 p=26,于是小编马上联系了出题人加上了这样的数据。
但出题人觉得这并没有彻底 hack 掉这种做法,因为将毒瘤代码中对 p=26 的特判删掉之后就可通过了。不信邪的出题人于是开始对着代码卡,注意到毒瘤在暴搜中的这句话具有关键作用:
if( idcnt > 1500000 ) return ;
其含义为,如果 idcnt 大于 1,500,000,就返回。即,如果 identity count 大于 1.5⋅106,就退出 dfs 函数,也即剪枝。那么我们能否构造一组数据,使得其有解,但 idcnt 到 1.5⋅106 的时候依然跑不出解呢?事实上这组数据是存在的,并且已经被出题人加入了最新数据中。但是出题人发现,把 1.5⋅106 改成 4⋅106,则毒瘤的代码又可以通过了!令人唏嘘。
更令人唏嘘的是,将毒瘤的代码与出题人代码进行对拍,约 100 组数据即可拍出错,但在洛谷上上传 200 组左右的数据实在是影响不好,故就此作罢。果然,毒瘤是不可战胜的。